Divisor Paths（gcd/数论）

题目 官方题解&代码

题意：给定一个数 d d d，利用该数造图，对于任意数 x , y < = d x,y y x->gcd(x,y),gcd(x,y)->y x−>gcd(x,y),gcd(x,y)−>y，且其过程中先增加/减少哪个素数不影响路径长度。任意选择，即按阶乘来计算。新get了STL的 a c c u m u l a t e accumulate accumulate函数。

#include
using namespace std;
#define ll long long

const int mod = 998244353;

void mul(int &a,int b) {
	a = 1LL*a*b%mod;
}
int quickp(int a,int p) {
	int res = 1;
	while(p) {
		if(p&1) mul(res,a);
		mul(a,a);
		p >>= 1;
	}
	return res;
}
int main() {
	ll d,x,y;
	scanf("%I64d",&d);
	int q;
	scanf("%d",&q);
	vector primes;
	for(ll i = 2;i*i  1) primes.push_back(d);
	vector fac(100),rfac(100);
	fac[0] = 1;
	for(int i = 1;i = 0;--i)
		mul(rfac[i] = rfac[i+1],i+1);
	while(q--) {
		scanf("%lld%lld",&x,&y);
		vector up,dw;
		for(auto p : primes) {
			int cnt = 0;
			while(x%p == 0) {
				--cnt;
				x /= p;
			}
			while(y%p == 0) {
				++cnt;
				y /= p;
			}
			if(cnt  0) up.push_back(cnt);
		}
		int ans = 1;
		mul(ans,fac[accumulate(up.begin(),up.end(),0)]);
		for(auto v : up) mul(ans,rfac[v]);
		mul(ans,fac[accumulate(dw.begin(),dw.end(),0)]);
		for(auto v : dw) mul(ans,rfac[v]);
		printf("%d\n",ans);
	} 
	return 0;
}