急に大量に問題が増えてびっくり。
https://yukicoder.me/problems/no/1164
問題
整数A,B,Nが与えられる。
を(10^9+7)で割った余りを求めよ。
解法
f(n) := gcd(*)がnの倍数になるiの組み合わせの数
g(n) := gcd(*)がnになるiの組み合わせの数
とする。求めたいのはである。
f(n)が求まれば、f(n)=g(n)+g(2n)+g(3n)+....なので、g(n)を大きい順に求めて行くことができる。
あとはf(n)を求めよう。
A~Bの間にあるnの倍数をk個とすると、f(n)=k^Nとなる。
なお、g(n)はあとでjの累乗の時に用いるので、f(n)・g(n)を求めるときはmod 10^9+6で求めるようにすること。
int A,B,N; const ll mo1=1000000006; const ll mo=1000000007; ll modpow1(ll a, ll n) { ll r=1;a%=mo1; while(n) r=r*((n%2)?a:1)%mo1,a=a*a%mo1,n>>=1; return r; } ll modpow(ll a, ll n) { ll r=1;a%=mo; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } ll dp[10101011]; void solve() { int i,j,k,l,r,x,y; string s; cin>>A>>B>>N; ll pn=0; ll v=0; ll ret=1; for(i=B;i>=1;i--) { int num=B/i-(A-1)/i; if(num==pn) { dp[i]=v; } else { pn=num; dp[i]=v=modpow1(num,N); } for(j=i*2;j<=B;j+=i) { dp[i]-=dp[j]; } (dp[i]=dp[i]%(mo-1)+(mo-1))%=(mo-1); if(dp[i]) (ret*=modpow(i,dp[i]))%=mo; } cout<<ret<<endl; }
まとめ
ここら辺は典型かな。