Submit: 1206 Solved: 747
对于正整数n，定义f(n)为n所含质因子的最大幂指数。例如f(1960)=f(2^3 * 5^1 * 7^2)=3, f(10007)=1, f(1)=0。
给定正整数a,b，求sigma(sigma(f(gcd(i,j)))) (i=1..a, j=1..b)。
Input
第一行一个数T，表示询问数。
接下来T行，每行两个数a,b，表示一个询问。
Output
对于每一个询问，输出一行一个非负整数作为回答。
Sample Input
4
7558588 9653114
6514903 4451211
7425644 1189442
6335198 4957
7558588 9653114
6514903 4451211
7425644 1189442
6335198 4957
Sample Output
35793453939901
14225956593420
4332838845846
15400094813
14225956593420
4332838845846
15400094813
HINT
【数据规模】
T<=10000
1<=a,b<=10^7
Solution
莫比乌斯反演。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #define ll long long using namespace std; const int N=10000007; int T,tot,Min[N],Max[N],Num[N],a[N],b[N],c[N],prime[N],ans[N],sum[N]; void pre() { ans[1]=0; for (int i=2;i<=10000000;i++) { if (!Min[i]) { Min[i]=min(Min[c[i]],b[i]); Max[i]=max(Max[c[i]],b[i]); Num[i]=Num[c[i]]+1; } if (!a[i]) { prime[++tot]=i; a[i]=tot; b[i]=1; c[i]=1; long long t=i;int s=0; while (t<=10000000) { s++; Max[t]=Min[t]=s; Num[t]=1; t*=i; } } for (int j=1;j<=tot&&i*prime[j]<=10000000&&j<=a[i];j++) { a[i*prime[j]]=j; if (a[i]==j) { b[i*prime[j]]=b[i]+1; c[i*prime[j]]=c[i]; }else { b[i*prime[j]]=1; c[i*prime[j]]=i; } } } for (int i=2;i<=10000000;i++) if (Max[i]==Min[i]) { if (Num[i]&1) ans[i]=1;else ans[i]=-1; } for (int i=1;i<=10000000;i++) sum[i]=sum[i-1]+ans[i]; } ll calc(int x,int y) { ll ans=0;int j; for (int i=1;i<=x&&i<=y;i=j+1) { j=min(x/(x/i),y/(y/i)); ans+=(ll)(sum[j]-sum[i-1])*(x/i)*(y/i); } return ans; } int main() { scanf("%d",&T); pre(); for (int i=1;i<=T;i++) { int x,y; scanf("%d%d",&x,&y); printf("%lld\n",calc(x,y)); } return 0; } |
