对于正整数,n,将g(n)定义为整除n的最大完全平方数。

例如,g(18)=9,g(19)=1。

同时定义

S(N)=sum(N g(N)){N=1~N}

例如,S(10)=24和S(100)=767。

计算S(10^{14})mod 1000000007。

测试脚本

import math
import time
li=[] 
def Sieve(n):
 h  = [True] * n
 h[:2] = [False, False]
 for i in range(2, int(n ** 0.5) + 1):
    if h[i]:
        h[i*i::i] = [False] * len(h[i*i::i]) #相当于步长为i的循环
 for i, e in enumerate(h):
    if e:
        li.append(i)

li=[] 
def f3(m):
 x=[1 for i in range(0,m+1)]
 Sieve(int(m**0.5))
 for i in li:
  for j in range(1,int(math.log(m,i)/2)+1):
   n=i**(2*j)
   for k in range(1,int(m/n)+1):
     x[n*k]*=(i**2)
 s=0
 for i in range(1,m+1):s+=x[i]
 return s

t=time.time();f3(10**8);print(time.time()-t)
724475280152
41.73160362243652