裸的莫比乌斯反演
1 #include<bits/stdc++.h> 2 #define N 100005 3 #define M 10000005 4 #define LL long long 5 #define inf 0x3f3f3f3f 6 using namespace std; 7 inline int ra() 8 { 9 int x=0,f=1; char ch=getchar(); 10 while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();} 11 while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();} 12 return x*f; 13 } 14 int a,b,c,d,n,ans,cnt; 15 int mo[N],prime[N],sum[N]; 16 bool vis[N]; 17 void mobius() 18 { 19 mo[1]=1; 20 for (int i=2; i<=50005; i++) 21 { 22 if (!vis[i]) prime[++cnt]=i,mo[i]=-1; 23 for (int j=1; j<=cnt && i*prime[j]<=50005; j++) 24 { 25 vis[i*prime[j]]=1; 26 if (i%prime[j]) mo[i*prime[j]]=-mo[i]; 27 else {mo[i*prime[j]]=0; break;} 28 } 29 } 30 for (int i=1; i<=50005; i++) 31 sum[i]=sum[i-1]+mo[i]; 32 } 33 int main() 34 { 35 n=ra(); mobius(); 36 while (n--) 37 { 38 a=ra(); b=ra(); d=ra(); 39 a/=d; b/=d; ans=0; 40 for (int i=1,pos; i<=min(a,b); i=pos+1) 41 { 42 pos=min(a/(a/i),b/(b/i)); 43 ans+=(sum[pos]-sum[i-1])*(a/i)*(b/i); 44 } 45 printf("%d ",ans); //cout<<ans RE....... 46 } 47 }