Description

Input

Output

Sample Input

2 4 4 3 10 10 5

Sample Output

20 148

Data Constraint

---

解题思路

来自（宋新波）莫比乌斯反演

---

Source Code

#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<cmath> using namespace std; const int N=100000; struct note { int n,m,a,ans,da; }; struct note2 { int x,y; }; note s[N]; note2 a[N]; int g[N],f[N],mu[N],t[N],prime[N]; int q,maxn; bool comp1(note x,note y) { return x.a<y.a; } bool comp2(note x,note y) { return x.da<y.da; } bool comp3(note2 x,note2 y) { return x.x<y.x; } void find() { memset(t,0,sizeof(t)); mu[1]=1; for (int i=2;i<=maxn;++i) { if (t[i]==0) { prime[++prime[0]]=i; mu[i]=-1; } for (int j=1;j<=prime[0];++j) { int tt=i*prime[j]; if (tt>maxn) break; t[tt]=1; if (i%prime[j]==0) {mu[tt]=0; break; } mu[tt]=-mu[i]; } } memset(f,0,sizeof(f)); int sq=floor(sqrt(maxn)); for (int i=1;i<=sq;++i) for (int j=i;j<=maxn;j+=i) { f[j]+=i; if ((j/i)>sq) f[j]+=j/i; } } int read() { int x=0,f=1; char ch=getchar(); while (ch<'0'|| ch>'9') { if(ch='-') f=-1; ch=getchar(); } while (ch>='0'&& ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*f; } void init() { q=read(); for (int i=1;i<=q;++i) { s[i].n=read(); s[i].m=read(); s[i].a=read(); s[i].da=i; s[i].ans=0; maxn=max(maxn,min(s[i].n,s[i].m)); } find(); //for (int i=1;i<=maxn;++i) printf("%d ",mu[i]); printf("\n"); //for (int i=1;i<=maxn;++i) printf("%d ",f[i]); printf("\n"); for (int i=1;i<=maxn;++i) { a[i].x=f[i]; a[i].y=i; } sort(s+1,s+q+1,comp1); sort(a+1,a+maxn+1,comp3); //for (int i=1;i<=maxn;++i) printf("%d %d\n",a[i].x,a[i].y); } void update(int x,int value) { for (int i=x;i<=maxn;i+=i&(-i)) g[i]+=value; } void insert(int d) { for (int i=1;i<=maxn/d;++i) if (mu[i]!=0) update(i*d,f[d]*mu[i]); } int getsum(int x) { int ans=0; for (int i=x;i>0;i-=i&(-i)) ans+=g[i]; return ans; } int main() { freopen("table.in","r",stdin); freopen("table.out","w",stdout); init(); int l=1; for (int k=1;k<=q;++k) { while (a[l].x<=s[k].a && l<=maxn) { insert(a[l].y); ++l; } //for (int i=1;i<=maxn;++i) printf("%d ",getsum(i)-getsum(i-1)); printf("\n"); int i,p,r; i=1; int n=min(s[k].n,s[k].m); int m=max(s[k].n,s[k].m); while (i<=n) { p=min(n/(n/i),m/(m/i)); r=getsum(p)-getsum(i-1); s[s[k].da].ans+=r*(n/i)*(m/i); i=p+1; } } for (int i=1;i<=q;++i) printf("%d\n",s[i].ans&0x7fffffff); fclose(stdin); fclose(stdout); }

PS

刚开始写的不够优美，只有70分，后来把lowbit（x）这个专门的函数去掉了，就过了。。。┭┮﹏┭┮