HDU 5780 BestCoder Round #85 gcd （数论---欧拉函数）

HDU 5780 BestCoder Round #85 gcd （数论---欧拉函数）

gcd

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 125    Accepted Submission(s): 41

Problem Description

Little White learned the greatest common divisor, so she plan to solve a problem: given x, n， query ∑gcd(xa−1,xb−1) (1≤a,b≤n)

Input

The first line of input is an integer T (1≤T≤300) For each test case ，the single line contains two integers x and n ( 1≤x,n≤1000000)

Output

For each testcase, output a line, the answer mod 1000000007

Sample Input

5 3 1 4 2 8 7 10 5 10 8

Sample Output

2 24 2398375 111465 111134466

Source

​​BestCoder Round #85​​

Recommend

wange2014   |   We have carefully selected several similar problems for you:  ​​5779​​​ ​​5775​​​ ​​5774​​​ ​​5773​​​ ​​5772​​

题意：给你x, n. 求

(1<=a,b<=n)

官方题解：

AC代码：

#includeusing namespace std;#define LL long longconst int N=1e6+5;const int mod=1e9+7;LL s[N];int prime[N],phi[N];void init() //筛法 { phi[1]=1; for(int i=2;i<=N;++i) { if(!phi[i]) { prime[++prime[0]]=i; phi[i]=i-1; } for(int j=1;j<=prime[0]&&i*prime[j]<=N;++j) { if(i%prime[j]) phi[i*prime[j]]=phi[i]*(prime[j]-1); else phi[i*prime[j]]=phi[i]*prime[j]; } } for(int i=1;i<=N;++i) phi[i]=(phi[i]+phi[i-1])%mod; s[1] = s[0] = 1; for(int i = 2;i < N;i++) s[i] = s[mod%i]*(mod-mod/i)%mod;}LL q_mod(LL x,LL n) //x^n:O(log(n))；{ LL res=1; while(n) { if(n & 1) res=(res*x)%mod; n>>= 1; x=(x*x)%mod; } return res;}LL solve(LL q,LL n){ if(q==1) return n; return (q_mod(q,n)-1)*s[q-1]%mod;}int main(){ init(); int t,x,n; scanf("%d",&t); while(t--) { scanf("%d%d",&x,&n); LL ans=0; for(int i=1,j;i<=n;i=j+1) { j = n/(n/i); LL sd = 2*phi[n/i]-1; ans = (ans + sd * (q_mod(x,i) * solve(x,j-i+1)%mod -(j-i+1)) % mod) % mod; } printf("%I64d\n",ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。