【反演复习计划】【COGS2432】爱蜜莉雅的施法
也是一个反演。
第一次手动推出一个简单的式子，激动.jpg
原题意思是求：
$Ans=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\phi(gcd(i,j))$
随意化几步试试：
$Ans=\sum\limits_{d=1}^{min(n,m)}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\phi(d)[gcd(i,j)==d]$
$Ans=\sum\limits_{d=1}^{min(n,m)}\sum\limits_{i=1}^{\frac{n}{d}}\sum\limits_{j=1}^{\frac{m}{d}}\phi(d*gcd(\frac{i}{d},\frac{j}{d}))[gcd(i,j)==1]$
提前$\phi(d)$函数
$Ans=\sum\limits_{d=1}^{min(n,m)}\phi(d)\sum\limits_{i=1}^{\frac{n}{d}}\sum\limits_{j=1}^{\frac{m}{d}}[gcd(i,j)==1]$
后面就是bzoj1101的形式了，随便化。
然后就可以分块了。
$\phi,\mu$可以前缀和，剩下的分块就好。
1 #include<bits/stdc++.h> 2 #define N 10000010 3 using namespace std; 4 typedef long long ll; 5 int n,m,prime[N],cnt,vis[N]; 6 ll f[N]; 7 void calcpre(){ 8 f[1]=1;cnt=0;memset(vis,1,sizeof(vis)); 9 for(int i=2;i<=N;i++){ 10 if(vis[i]){prime[++cnt]=i;f[i]=i-2;} 11 for(int j=1;j<=cnt;j++){ 12 int t=i*prime[j];if(t>N)break; 13 vis[t]=0;int p=prime[j]; 14 if (i%p)f[t]=f[i]*f[p]; 15 else{ 16 f[t]=(i/p)%p?f[i/p]*(p-1)*(p-1):f[i]*p; 17 break; 18 } 19 } 20 } 21 for(int i=2;i<=N;i++)f[i]+=f[i-1]; 22 } 23 inline int read(){ 24 int f=1,x=0;char ch; 25 do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9'); 26 do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9'); 27 return f*x; 28 } 29 int main(){ 30 freopen("aimiliyausemagic.in","r",stdin); 31 freopen("aimiliyausemagic.out","w",stdout); 32 calcpre();int T=read(); 33 while(T--){ 34 n=read();m=read(); 35 if(n>m)swap(n,m);ll ans=0; 36 for(int i=1,j=1;i<=n;i=j+1){ 37 j=min(n/(n/i),m/(m/i)); 38 ans+=(f[j]-f[i-1])*(n/i)*(m/i); 39 } 40 printf("%lld\n",ans); 41 } 42 return 0; 43 }优质内容筛选与推荐>>
1、另一个程序正在使用此文件，进程无法访问
2、iOS开发如何提高(from 唐巧的博客)
3、机器学习入门(三)
4、【转】asp.net向客户端注册JavaScript脚本的三种方法
5、命令行中开启mySQL数据库服务