神の安♂排

降序排序

因子平方和

def fo(n): fn = 0 for i in range(1, n+1): if n % i == 0: fn += pow(i, 2) return fn FN = 0 for each in range(1, N+1): FN += fo(each) print(FN)

有没有大佬看看这样为什么不通过55

# 利用平方和公式 1^2 + 2^2 + 3^2 + ... + N^2 = （N *（N+1）*（2N+1）） // 6# F(N) 计算中 1^2 有N//1个， 2^2有N//2个，3^2有N//3个，..., N^2 有N//N个s = (N * (N + 1) * (2*N + 1)) // 6 ls = ( i * i * (N // i - 1) for i in range(1, N//2+1)) s += sum(ls) print(s)

用平方和公式 与生成器表达式之和成功

<pre><code>def get_sum(n): return n * (n + 1) * (2 * n + 1) // 6 # 这个和就是i^2*(N//i)相加的和，但是从头算到尾会提示复杂度高 # 这样计算，所有的数里面，可以凑成1个从1到N^2的和，然后，除去这部分，又可以凑出一个从1到(N//2)^2的和，依此类推 # 与N//i有关，就拆成两部分，只关注根号N以前，分别凑成从1到N//i的和，用公式算 # 再计算从1到根号N这部分，将凑成公式那部分除去，剩余个数的和，逐个累加。 sum = 0 for i in range(1, int(N ** 0.5) + 1): sum += i * i * (N // i - int(N ** 0.5)) + get_sum(N // i) print(sum)</code></pre>

复杂度可以降低到根号N，就通过了。

<a href="http://www.gznb.xyz/posts/pythonTip-52-因子平方和/">题解： http://www.gznb.xyz/posts/pythonTip-52-因子平方和/</a>

<pre style="background-color:#ffffff;color:#000000;font-family:'Consolas';font-size:15.0pt;">import sys
sys.setrecursionlimit(10000000) # 提高python的默认递归深度

def yinzi(n):
 I = []
 for i in range(1, n+1):
 if n % i == 0:
 I.append(i)
 return I


def f(n):
 sum = 0
 for i in yinzi(n):
 sum += i**2
 return sum


def F(n):
 if n == 1:
 return 1
 else:
 return f(n) + F(n-1)


print(F(100))
</pre>

循环基本都会超（高精度的题目）

新手超时解法。。请大佬们帮忙改进

详情请跳转：<a href="https://blog.csdn.net/Herishwater/article/details/95488137">https://blog.csdn.net/Herishwater/article/details/95488137</a>

参考前人的进行总结

1、先试试每个 x的平方，在每一位会出来几次。2、发现 次数=N/位数 &nbsp;（整除），想想容易明白。比如，比19小的数字，几个有因子3（第三位是几）？从3开始，3,6,9,12，15,18，就是19/33、前面的数字变得快，后面的数字有重复。关键就是从重复的数字里再观察哪一位，这个次数会发生变化.发现刚好也是这个次数=N/位数&nbsp; &nbsp;拿18举例 &nbsp;[18, 9, 6, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1】&nbsp; &nbsp;发现第二位是9,=18/2 &nbsp; 而第9位，又刚好是2结束的位置，仔细想想，这个也是容易想明白原因的。如果第10位还是2，那根据第二条的发现，2=次数应该等于N/位数=18/10 &nbsp;因为2比9小，所以这不合理。4、找到这2个规矩，然后根据这个数列特点，前半段不重复，直接一个个算x的平方再乘系数容易， &nbsp; &nbsp; &nbsp; 后半段重复多，用公式算 平方和容易。而这个把数列切开的位置，应该就在平方根附近。也容易想明白， def ss(n): &nbsp; &nbsp; return n*(n+1)*(2*n+1)/6 t=int(N**(1/2.0)) s=0 for i in range(1,t+1): &nbsp; &nbsp;s=s+ss(N/i)+N/i*(i**2) s=s-t*ss(t) print s

一点心得

def f(N):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; y=0 &nbsp; &nbsp; for i in range(1,N+1): &nbsp; &nbsp; &nbsp; &nbsp; if N%i==0: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; y+=i**2 &nbsp; &nbsp; return y&nbsp; &nbsp;&nbsp; F=0 for i in range(1,N+1): &nbsp; &nbsp; F+=f(i) &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; print(F)

还是超时

def f(n): &nbsp; L=[1,n] &nbsp; temp=n-1 &nbsp; temp1=2 &nbsp; while temp&gt;0: &nbsp;&nbsp;&nbsp; if n%temp1==0: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; L=L+[temp1,n/temp1] &nbsp;&nbsp;&nbsp; temp=n/temp1-temp1 &nbsp;&nbsp;&nbsp; temp1+=1 &nbsp; lis=list(set(L)) &nbsp; sm=0 &nbsp; for x in lis: &nbsp;&nbsp;&nbsp; sm+=x**2 &nbsp; return sm def F(n): &nbsp; smu=0 &nbsp; for y in range(1,n+1): &nbsp;&nbsp;&nbsp; smu+=f(y) &nbsp; return smu result = F(N) print result

还是复杂度高啊

def f(n): &nbsp; L=[] &nbsp; for i in range(1,n+1): &nbsp;&nbsp;&nbsp; if n%i==0: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; L.append(i) &nbsp; sum1=0 &nbsp; for x in L: &nbsp;&nbsp;&nbsp; sum1+=x**2 &nbsp; return sum1 def F(n): &nbsp; summ=0 &nbsp; for i in range(1,n+1): &nbsp;&nbsp;&nbsp; summ+=f(i) &nbsp; return summ print F(N)

算法复杂度过高的代码

s = (N * (N + 1) * (2*N + 1)) // 6ls = ( i * i * (N // i - 1) for i inrange(1, N//2+1))s += sum(ls)print(s)

通过了

a=int(input()) ls=[] ls2=[] for i in range(a): i+=1 if a%i==0: ls.append(i) b=len(ls) for i in range(b): d=ls[i] d=d**2 ls2.append(d) c=sum(ls2) print(c)

我有一种解答，不过在这个网站中不适用，会直接报错。

老是做不对，变量为啥不能复制？求解答。

ohNo

复杂度过高print(sum([sum([x*x for x in range(1,y+1) if y%x==0]) for y in range(1,N+1)]))

。。。就是因为循环太简单了n^2的复杂度不超时就出鬼了。。

def F(y): 	sum=1 	for i in range(2,y+1): 		s=1 		for j in range(2,i+1): 			if i%j==0: 				s+=j*j 		sum+=s 	return sum print F(N)

为什么把这么简单的循环说超时？？？

解题之出，用一行代码，根本过不了，超过一万就得等好久后来开始想怎么优化，不能递归，得找规律，于是有 了下面的代码<pre style="background-color:#404040;color:#9bc28e;font-family:'宋体';font-size:10.5pt;">for i in xrange(1,n+1):
 num +=(n/i) * (i**2)</pre><pre style="background-color:#404040;color:#9bc28e;font-family:'宋体';font-size:10.5pt;">
</pre>虽然时间减少了也能执行到千万了，但还是不通过，但思路还是对的，下面就详细说说 --------------------------------------------------分割线---------------------------------------------------------------首先思路当n=100的时候，1的倍数有100个，所以1是这100个数的因子，所以要平方100次，2的倍数是100/2=50个，以此类推，直到50的倍数有 两个，50以上全部都是一个可以把这个算法写成两部分1**2 * n/1 + 2**2 * n/2 +....... + (n/2)**2 * n/(n/2) &nbsp; &nbsp; &nbsp;+ &nbsp; &nbsp; &nbsp; &nbsp;(n/2)**2+.....n**2前半部分用循环 &nbsp;后半部分用平方和公式（n*(n+1)(2n_1))/6前半部分好写<pre style="color: rgb(155, 194, 142); font-family: 宋体; font-size: 10.5pt; background-color: rgb(64, 64, 64);">for i in xrange(1,n/2+1):
 num +=(n/i) * (i**2)</pre>后半部分平方和是从（N/2）**2到N**2所以要用从1**2到N**2 减掉 1**2到（N/2）**2这部分写起来太多了，我就不写了就是因为太多了，我嫌写的多，所以我把前半部分改了一下<pre style="font-family: 宋体; font-size: 10.5pt; background-color: rgb(64, 64, 64);">(n/i) * (i**2) 变成 (n/i -1) * (i**2)</pre>这样就有一个完整的平方和，就不用减了于是代码如下<pre style="background-color:#404040;color:#9bc28e;font-family:'宋体';font-size:10.5pt;">n=10000000
num=0
for i in xrange(1,n/2+1):
 num +=(n/i-1) * (i**2)
num += (n*(n+1)*(2*n+1))/6
print num</pre>当n=一千万的时候 执行时间7.354177 s一亿的时候73秒提交代码还是超时然后换成def<pre style="background-color:#404040;color:#9bc28e;font-family:'宋体';font-size:10.5pt;"></pre><pre style="background-color:#404040;color:#9bc28e;font-family:'宋体';font-size:10.5pt;">def f(n):
 num = 0
 for i in xrange(1,n/2+1):
 num +=(n/i-1) * (i**2)
 num += (n*(n+1)*(2*n+1))/6
 return num
n=100000000
print f(n)</pre><pre style="background-color:#404040;color:#9bc28e;font-family:'宋体';font-size:10.5pt;"></pre>一千万的执行时间6.548960 s 一亿65.644598 s提交代码竟然通过了 一亿运行结果&nbsp;400685641565621401132515 数字挺大<pre style="background-color:#404040;color:#9bc28e;font-family:'宋体';font-size:10.5pt;">
</pre>

终于过了

print sum([N/x*x**2 for x in range(1,N+1)])就遍历了一次，还是超时。。。没想明白

就遍历了一次，还是超时。。。没想明白

我自己写的一段，在EClipse上运行ok，在这个网页上就是不通过，无语了import math def factor(N): &nbsp;&nbsp;&nbsp; L=[] &nbsp;&nbsp;&nbsp; for i in range(1,N+1): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if N%i==0: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; L.append(i) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; continue &nbsp;&nbsp;&nbsp; return L def f(L): &nbsp;&nbsp;&nbsp; squaresum = 0 &nbsp;&nbsp;&nbsp; for i in range(0,len(L)): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; squaresum=squaresum+L[i]*L[i] &nbsp;&nbsp;&nbsp; return squaresum def F(N): &nbsp;&nbsp;&nbsp; fsum = 0 &nbsp;&nbsp;&nbsp; for i in range(0,N): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; fsum = fsum + f(factor(i)) &nbsp;&nbsp;&nbsp; return fsum

求解

不要一个一个算，整体来看，F(N)必然包括N个1**2，N//2个2**2,N//3个3**2....&nbsp; 然后从N/2+1开始，就只有一个n**2，在统计2**2时可以统计出相应的（N//2）**2，优化一下么就可以O（sqrt（N））做到 。然后我写了以下代码：sum([N//i*i*i &nbsp;for i in range(1,N+1)]) &nbsp;，还是超时 &nbsp; &nbsp; &nbsp; &nbsp;

第52题：因子平方和

输出字典key

求中位数

字符串编辑

百度时间