/**//* 題意:原題可轉化為求在n*m范圍內 n m ∑∑ 2*(gcd(x,y)-1)+1 x=1 y=1 感覺挺像visible trees的用容斥做,但不會容斥做 看了 http://hi.baidu.com/570193465/blog/item/d4219303d7b43e1c738b6547.html O(nsqrt(n)) 對于上式,重點是求出 t=gcd(x,y) 時的(x,y)對數 可以枚舉gcd 記錄cnt[i] = (n/i)*(m/i) 即公約數是i的倍數(k*i)的對數 然后再調整cnt[i],使其表示公約數是i的對數 cnt[i]-=cnt[k*i]即可! */ #include<cstdio> #include<cstring> inline int min(int a,int b){return a<b?a:b;} constint MAXN =100010; longlong cnt[MAXN]; int main() { int n,m; while(~scanf("%d%d",&n,&m)) { int t = min(n,m); for(int i=2;i<=t;i++)//gcd = i cnt[i] = (longlong)(n/i)*(m/i);//cnt[i] : the number of whose gcd is k*i for(int i=t;i>=1;i--) for(int k=2;k*i<=t;k++) cnt[i]-=cnt[k*i];//to get the real number of whose gc is i longlong ans =0; for(int i=1;i<=t;i++) ans+=2*(i-1)*cnt[i]; printf("%I64d\n",ans+(longlong)n*m); } return0; }
那個是看別人寫的 #_#