SRM 613 DIV1 Middle - RandomGCD (復習x)
問題
lowからhighまでの数字のうち、最大公約数がKとなるようにN個の数字の集合を作る。
このとき、同じ数字を何回選んでもよい。
このとき、数字の選び方が何通りあるか求める。
解き方
最大公約数がＫということは、lowからhighまでのうちKの倍数であるものだけを考えたらよい。
そしてそのうち、それぞれが約数を持たないような全ての場合の数を求めればよい。
このときの効率的な求め方が思い浮かばなくEditorialを読む。
Ｋの倍数だけを考えたらよいということは、lowからhighまでの数字をKで割ったものについて考えれば単純化できる。
さらにその中でｄｐを利用することで約数を持たないような数を求めることができる。
最初にＫで割ったときにlowが１となったときは、すべて１を選んだときの場合の数１通りを足すことに注意。
ＭＯＤを使う際は、ＭＯＤする前にオーバーフローすることがあるのでlong long型に変換する。
オーバーフローしないよう、毎回の計算をＭＯＤすることにも注意。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int dp[100010];
int MOD=1000000007;
class RandomGCD {
public:
int f(int a,int b){
int ret=1,cur=a;
while(b){
if(b&1)ret=(long long)ret*cur%MOD;
cur=(long long)cur*cur%MOD;
b>>=1;
}
return ret;
}
int countTuples(int N, int K, int low, int high) {
low=(low+K-1)/K;
high=high/K;
if(low>high)return 0;
memset(dp,0,sizeof(dp));
for(int i=100000;i>=1;i--){
int L=(low+i-1)/i;
int H=high/i;
if(L<=H){
dp[i]=f(H-L+1,N);
dp[i]-=(H-L+1);
if(dp[i]<0)dp[i]+=MOD;
for(int j=i*2;j<=100000;j+=i){
dp[i]-=dp[j];
if(dp[i]<0)dp[i]+=MOD;
}
}
}
if(low==1)dp[1]=(dp[1]+1)%MOD;
return dp[1];
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int dp[100010];
int MOD=1000000007;
class RandomGCD {
public:
int f(int a,int b){
int ret=1,cur=a;
while(b){
if(b&1)ret=(long long)ret*cur%MOD;
cur=(long long)cur*cur%MOD;
b>>=1;
}
return ret;
}
int countTuples(int N, int K, int low, int high) {
low=(low+K-1)/K;
high=high/K;
if(low>high)return 0;
memset(dp,0,sizeof(dp));
for(int i=100000;i>=1;i--){
int L=(low+i-1)/i;
int H=high/i;
if(L<=H){
dp[i]=f(H-L+1,N);
dp[i]-=(H-L+1);
if(dp[i]<0)dp[i]+=MOD;
for(int j=i*2;j<=100000;j+=i){
dp[i]-=dp[j];
if(dp[i]<0)dp[i]+=MOD;
}
}
}
if(low==1)dp[1]=(dp[1]+1)%MOD;
return dp[1];
}
};
