abc212G - Power Pair

标签：frac Power sum dfs abc212G ans Pair mo lld

G - Power Pair

如果知道了原根的话这题就会简单很多
r是p的原根

\(r^a=x, r^b=y\)
那么$$r^{an} \equiv r^b (mod\ p) $$
根据原根的性质

\[an \equiv b(mod\ p-1) \]

\[an-k(p-1)=b \]

令n=p-1
由裴蜀定理得\((a,n)|b\)

\[ans=\sum_{a=1}^n \frac{n}{(n,a)} \]

\[=\sum_{d|n}\frac{n}{d} \sum_{i=1}^n[(i,n)==d] \]

\[=\sum_{d|n}\frac{n}{d} \sum_{i=1}^{\frac{n}{d}} [(i,\frac{n}{d})==1] \]

\[=\sum_{d|n}d \varphi(d) \]

那么最后这个直接dfs算即可。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))

using namespace std;
typedef double db;
typedef long long ll;
const int N = 2e5 + 5;
const ll inf = 1ll << 60;
const ll mo = 998244353;
ll n, ans, tot;
ll p[N], c[N];
void solve() {
	ll mx = sqrt(n) + 1;
	fo(i, 2, mx) {
		if (n % i == 0) {
			p[++tot] = i;
			while (n % i == 0) {
				c[tot]++;
				n /= i;
			}
		}
	}

	if (n != 1) {
		p[++tot] = n%mo;
		c[tot] = 1;
	}
}
void dfs(int x, ll y) {
	if (x > tot) {
		ans = (ans + y )%mo;
		return;
	}
	
	dfs(x+1,y);
		
	ll t=1;
	fo(i,1,c[x]) {
		dfs(x+1, y*t%mo*t%mo*p[x]%mo *(p[x]-1)%mo);
		t=t*p[x]%mo;
	}
	
}
int main()
{

//	freopen("data.in","r",stdin);
	
	scanf("%lld", &n);
	n--;
	solve();
	
//	fo(i,1,tot) printf("%lld %lld\n",p[i],c[i]);

	ans = 1;
	dfs(1, 1);

	printf("%lld", ans);

	return 0;
}

 

标签：frac,Power,sum,dfs,abc212G,ans,Pair,mo,lld
From： https://www.cnblogs.com/ganking/p/17734590.html