original link - http://acm.hdu.edu.cn/showproblem.php?pid=6706
题意：
求 f ( n , a , b ) = ∑ i = 1 n ∑ j = 1 i g c d ( i a ? j a , i b ? j b ) [ g c d ( i , j ) = 1 ] % ( 1 0 9 + 7 ) f(n,a,b)=\sum_{i=1}^n \sum_{j=1}^i gcd(i^a-j^a,i^b-j^b)[gcd(i,j)=1]\%(10^9+7) f(n,a,b)=∑i=1n?∑j=1i?gcd(ia?ja,ib?jb)[gcd(i,j)=1]%(109+7)
解析：
由于 a , b a,b a,b互质，所以有 g c d ( i a ? j a , i b ? j b ) = i ? j gcd(i^a-j^a,i^b-j^b)=i-j gcd(ia?ja,ib?jb)=i?j。
f ( n , a , b ) = ∑ i = 1 n i ? ∑ j = 1 i [ g c d ( i , j ) = 1 ] ? ∑ i = 1 n ∑ j = 1 i j [ g c d ( i , j ) = 1 ] f(n,a,b)=\sum_{i=1}^n i*\sum_{j=1}^i[gcd(i,j)=1]-\sum_{i=1}^n \sum_{j=1}^ij[gcd(i,j)=1] f(n,a,b)=i=1∑n?i?j=1∑i?[gcd(i,j)=1]?i=1∑n?j=1∑i?j[gcd(i,j)=1]
f ( n , a , b ) = ∑ i = 1 n i ? ? ( i ) ? ∑ i = 1 n i ? ? ( i ) ? [ i = 1 ] 2 f(n,a,b)=\sum_{i=1}^n i*\phi(i)-\sum_{i=1}^n \dfrac{i*\phi(i)-[i=1]}{2} f(n,a,b)=i=1∑n?i??(i)?i=1∑n?2i??(i)?[i=1]?
f ( n , a , b ) = ∑ i = 1 n i ? ? ( i ) ? 1 2 f(n,a,b)=\dfrac{\sum_{i=1}^ni*\phi(i)-1}{2} f(n,a,b)=2∑i=1n?i??(i)?1?
令 F ( n ) = i ? ? ( i ) ,
A n s ( n ) = ∑ i = 1 n i ? ? ( i ) ,
g ( i ) = i F(n)=i*\phi(i),\;
Ans(n)=\sum_{i=1}^ni*\phi(i),\;
g(i)=i F(n)=i??(i),Ans(n)=∑i=1n?i??(i),g(i)=i
可以推得：
A n s ( n ) = ∑ i = 1 n ( F ? g ) ( i ) ? ∑ d = 2 n g ( d ) A n s ( n / d ) g ( 1 ) Ans(n)=\dfrac{\sum_{i=1}^{n}(F*g)(i)-\sum_{d=2}^{n}g(d)Ans(n/d)}{g(1)} Ans(n)=g(1)∑i=1n?(F?g)(i)?∑d=2n?g(d)Ans(n/d)?
其中：
∑ i = 1 n ( F ? g ) ( i ) = ∑ i = 1 n ∑ d ∣ i F ( d ) ? g ( i d ) = ∑ i = 1 n ∑ d ∣ i i ? ? ( d ) = ∑ i = 1 n i 2 \sum_{i=1}^{n}(F*g)(i)=\sum_{i=1}^{n}\sum_{d|i}F(d)*g(\frac{i}{d})=\sum_{i=1}^{n}\sum_{d|i}i*\phi(d)=\sum_{i=1}^ni^2 i=1∑n?(F?g)(i)=i=1∑n?d∣i∑?F(d)?g(di?)=i=1∑n?d∣i∑?i??(d)=i=1∑n?i2
【数论/数学|huntian oy（杜教筛 欧拉函数）】代码：
/*
*Author : Jk_Chen
*Date : 2019-08-25-15.37.26
*/
#include
using namespace std;
#define LL long long
#define rep(i,a,b) for(int i=(int)(a);
i<=(int)(b);
i++)
#define per(i,a,b) for(int i=(int)(a);
i>=(int)(b);
i--)
#define mmm(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define pill pair
#define fi first
#define se second
#define debug(x) cerr<<#x<<" = "<='0' && ch<='9'))last=ch,ch=getchar();
while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
if(last=='-')ans=-ans;
return ans;
}
/*_________________________________________________________head*/LL Pow(LL a,LL b,LL mod){
LL res=1;
while(b>0){
if(b&1)res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}int pri[maxn],now,phi[maxn];
bool vis[maxn];
void init(){
phi[1]=1;
rep(i,2,maxn-1){
if(!vis[i]){
pri[++now]=i;
phi[i]=i-1;
}
for(int j=1;
j<=now&&pri[j]*iMap;
LL Ans(LL n){
if(n 推荐阅读
- HDU 5528【2015长春现场赛 B】 Count a * b
- 类欧几里得算法|[类欧几里得算法 数论] BZOJ 2987 Earthquake
- [数论] Codeforces 819D R #421 D.Mister B and Astronomers & 516E R #292 E. Drazil and His Happy Friends
- 模板 poj2947 Widget Factory 高斯消元
- 【扩展欧几里得】练习题
- 扩展欧几里得【数论
- 数论|hdu 5322 Hope（分治+NTT）
- HDU 5528 Count a × b
- 线性同余方程组
- 数论|AtCoder Beginner Contest 156 C.Rally