[SPOJ LCMSUM]数论

【题目大意】
求LCM(1,N)+LCM(2,N)+LCM(3,N)+…+LCM(N,N)
【算法分析】
ans=n*(1/gcd(1,n)+2/gcd(2,n)+…+n/gcd(n,n))
其中显然gcd(x,n)都是n的约数。
然后我们都知道n的约数的个数是n^0.5级别的。
于是可以考虑把分母相同的合并。
然后设x为n的一个约数，那么(kx,n)=x 当且仅当满足 (k,n/x)=1
然后再有不等式kx<=n 即 k<=n/x。
然后。。。
k<=n/x   (k,n/x)=1     想到了什么？
欧拉函数~
设t=n/x
但是现在要求的是所有满足  (k<=t)&& (k,t)=1  的k的和。
然后我们来证一个性质。
那个和=t*phi(t)/2。

假设：gcd(x,t)=g && g>1
那么gcd(t-x,t)%g=0
为什么？
∵t%g=0   x%g=0  ∴ (t-x) % g=0。
所以可以利用反证法得出，假如(x,t)=1那么 (t-x,t)=1
于是互质的数都是成对的，且他们的和是t。
所以总体来说可以分成phi(t)/2组，每组的和为t，所以总和为t*phi(t)/2。

但是如果t为偶数的话，有可能出现t/2算两次的情况之类。
但是显然，t为偶数时，t/2和t不互质，不会算进欧拉函数里，所以不用考虑。

然后最后的做法是：
1、
用筛法把1e6的素数和欧拉函数都筛出来。 这一步的时间复杂度是O(1e6 lg 1e6)。
这个时间复杂度可能很多人会说= =，但是至少我在网上看到的筛法好像都是O(n lg n)的复杂度的。
虽然他们叫线性筛，我也一直认为是线性的，直到APIO听了CDQ讲课，其中有一个典型的复杂度分析就是我这种写法的筛。最后的结论是O(n lg n)。。。
2、
先求n的所有约数，然后利用上面的性质求和。
但是这题异常猥琐，时间非常紧，要先用筛出的素数对n分解质因数，然后再DFS求约数。
一开始我过于信任SPOJ的机子，直接一个for过去求约数，复杂度O(n^0.5)。
然后除了极限数据，我自己的机子卡着5s过。但是上面就不行了。

用了分解质因数以后，就由于那些素数的小步伐跳跃，卡过了。。。~

【时间复杂度】
O(1e6 lg 1e6+ ( T(n^0.5) + lg n )*TestCaseNum)。
其中T(x)函数表示<=x的数里的素数个数。
然后第二步如果是我本来那种直接暴力找约数的话，那么复杂度就是
O(1e6 lg 1e6+ ( n^0.5 + lg n)*TestCaseNum)。
最终，由于TestCaseNum把常数无限放大，我的暴力悲剧地TLE了。。。
【其它】
在HWG的博客看到这题。。。于是做了一下，没想到被常数卡成SB了。。。
Orz，一开始以为A|B是AB互质的意思，现在已经修正。。。
【CODE】
#include #include #include typedef long long lld;
const int N=1000001;
int n,Tc,pt,Lt,sum;
bool prime[N];
int phi[N],pl[N],L[N],Num[N];
lld ans;
char ss[200];

void init(){
memset(prime,true,sizeof(prime));
pt=0;
int i,j;
for (i=1;i for (i=2;i for (pl[++pt]=i,j=i;j phi[j]=phi[j]/i*(i-1);
prime[j]=false;
}
}

void Div(int x){
Lt=0;
for (int i=1;(pl[i]*pl[i]<=n) && (x!=1);i++){
if (x%pl[i]==0) {L[++Lt]=pl[i]; Num[Lt]=0;} else continue;
while (x%pl[i]==0){
Num[Lt]++;
x/=pl[i];
}
}
}

void dfs(int dep){
if (dep>Lt){
ans+=((lld)(phi[sum])*sum)>>1;
if (sum*sum!=n) ans+=((lld)(phi[n/sum])*(n/sum))>>1;
return;
}
int tmp=sum;
dfs(dep+1);
for (int i=1;i<=Num[dep];i++){
sum*=L[dep];
if (sum>n/sum) break;
dfs(dep+1);
}
sum=tmp;
}

void Write(){
int tt=0;
while (ans){
ss[tt++]=ans%10+’0′;
ans/=10;
}
for (int i=tt-1;i>=0;i–) putchar(ss[i]);
putchar(‘n’);
}

void solve(){
phi[1]=2;
sum=1;
ans=0;
Div(n);
dfs(1);
ans*=n;
printf("%lldn",ans);
}

void Read(int &x){
char ch;
for (ch=getchar();!(ch>=’0′ && ch<='9');ch=getchar());
x=0;
for (;ch>=’0′ && ch<='9';ch=getchar())
x=x*10+ch-‘0’;
}

int main(){
init();
Read(Tc);
int i;
for (i=1;i<=Tc;i++){
Read(n);
solve();
}
return 0;
}