本文主要是介绍【BZOJ2693】jzptab，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题解：
第一次学莫比乌斯反演就是死在了这道题上
这一次终于啃掉了
最后面的那个东西是一个积性函数，线性筛的时候计算，需要自己手推一下
总结几个小技巧：
1.分母不好处理可以想办法弄到分子上去
2.枚举一个数的倍数时可以直接用等比（差）等类似方法计算
3.积性函数扔到一起还是一个积性函数，在线性筛的时候可以预处理前缀和
//by sdfzchy
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int inf=(1<<30),N=10000010,mod=1e8+9;
int n,m;
inline int in()
{char ch=getchar();int f=1,tmp=0;while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') {tmp=(tmp<<1)+(tmp<<3)+(ch-'0');ch=getchar();}return tmp*f;
}
LL pri[N+10],pcnt,sum[N+10],h[N+10];
bool ok[N+10];void init()
{h[1]=1;for(int i=2;i<=N;i++){if(!ok[i]) pri[++pcnt]=i,h[i]=(i-(LL)i*i)%mod;for(int j=1;j<=pcnt&&i*pri[j]<=N;j++){ok[i*pri[j]]=1;if(i%pri[j]==0){h[i*pri[j]]=h[i]*pri[j]%mod;break;} h[i*pri[j]]=h[i]*h[pri[j]]%mod;}}for(int i=1;i<=N;i++) sum[i]=sum[i-1]+h[i],sum[i]%=mod;
}LL Sum(int x,int y)
{return ((LL)x*(x+1)/2%mod)*((LL)y*(y+1)/2%mod)%mod;
}LL calc(int x,int y)
{if(x>y) swap(x,y);LL ans=0;for(int i=1,p;i<=x;i=p+1){p=min(x/(x/i),y/(y/i));ans+=Sum(x/i,y/i)*(sum[p]-sum[i-1]);ans%=mod;}return (ans%mod+mod)%mod;
}int main()
{init();int T=in();while(T--) printf("%lld\n",calc(in(),in()));return 0;
}
这篇关于【BZOJ2693】jzptab的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
