#C241101A. 最大公约数

标签（Label）

动态规划
gcd

网址（Website）

题目详情 - 最大公约数 - Super

题解 - 最大公约数 - Super

题目（Problem）

样例解释

输入数据 1

3 2

输出数据 1

【样例1解释】
可能的数组有
${1, 1, 1}, {1, 1, 2}, {1, 2, 1}, {1, 2, 2}, {2, 1, 1}, {2, 1, 2}, {2, 2, 1}, {2, 2, 2}$，权值分别为 $1, 1, 1, 1, 1, 1, 1, 2$，总和为 $9$。

输入数据 2

3 200

输出数据 2

10813692

输入数据 3

100000 100000

输出数据 3

742202979

【样例4】
见选手目录下的 $gcd/gcd4.in$ 与 $gcd/gcd4.ans$。

【样例5】
见选手目录下的 $gcd/gcd5.in$ 与 $gcd/gcd5.ans$。

题解（Solution）

$\qquad$枚举 $g$ 表示当前 $\gcd$ ，很明显只有它的倍数能对它产生贡献，长度为 $n$ 的序列的贡献就是 $\verb!pow(n/i,n)!$ ，但是发现这样计算出来的 $\gcd$ 也有可能是当前 $g$ 的倍数，这个时候只需要从大到小计算，减去当前 $g$ 的倍数的答案就是当前的答案。

出题者题解

算法分析

考虑先枚举 $gcd$，假设其为 $x$，考虑计算 $gcd=x$ 的方案数，设为 $f_x$，首先计算 $gcd$ 为 $x$ 的倍数的方案数，这个其实就是 $\left\lfloor \frac{k}{x} \right\rfloor^n$。

那么我们要如何得到 $gcd=x$ 的方案呢，容斥一下，减去所有 $x$ 的倍数的方案就可以了，即 $\left\lfloor \frac{k}{x} \right\rfloor^n - \sum_{i>x,x|i} f_i$。

然后求 $\sum_{i=1}^k i f_i$ 就可以得到答案了。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9+7;
const int N = 101234;
bool ST;
inline void add(int &x,int y){if((x+=y)>=mod)x-=mod;}

int f[N],tmp[N];
int n,k,B,ans;

inline int ksm(int x,int k){
	int res=1;while(k){
		if(k&1) res=res*x%mod;
		x=x*x%mod, k>>=1;
	}return res;
}

void Solve(){
	n=rd(),k=rd();
	
	For(i,1,k) f[i] = ksm(k/i, n);
	Rof(i,k,1){
		for(int j=i*2;j<=k;j+=i)
			add(f[i], mod-f[j]);
	}
	For(j,1,k) add(ans, f[j]*j%mod);
	printf("%lld\n", ans);
} 

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("gcd.in","r",stdin);
	freopen("gcd.out","w",stdout);
	int T=1;double Tim=clock();
	while(T--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}