【BZOJ】3737: [Pa2013]Euler

题意：

求满足\(phi(a)=n\)的\(a\)的个数。（\(n \le 10^{10}\)）

分析

这种题一开始就感觉是搜索= =

题解

首先容易得到

\[\phi(n) = \prod_{i} p_i^{a_i-1} (p_i - 1)
\]

然后我们\(O(n^{0.5})\)预处理以下前\(n^{0.5}\)的素因子，然后再用\(O(n^{0.5}log(n))\)筛出大质数，然后从小到大一层一层搜下去即可，注意特判一下\(n=1\)的情况。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll N=1e10, Lim=1e5+5, Ml=1e9;

int tot, ans, p[Lim+5], np[Lim+5], pcnt;

ll b[5000005];

struct dat {

	ll p;

	int l;

}a[Lim<<1];

void init() {

	for(int i=2; i<=Lim; ++i) {

		if(!np[i]) p[pcnt++]=i;

		for(int j=0; j<pcnt; ++j) {

			int t=i*p[j];

			if(t>Lim) break;

			np[t]=1;

			if(i%p[j]==0) break;

		}

	}

}

ll rand(ll l, ll r) {

	static ll MD=1e9+7, g=78125, now=1998;

	now*=g; if(now>=MD) now%=MD;

	return l+now%(r-l+1);

}

ll mul(ll a, ll b, ll m) { if(a<=Ml && b<=Ml) return a*b%m; if(b>a) swap(b, a); ll x=0; for(; b; b>>=1, a=(a+a)%m) if(b&1) x=(x+a)%m; return x; }

ll ipow(ll a, ll b, ll m) { ll x=1; for(; b; b>>=1, a=mul(a, a, m)) if(b&1) x=mul(x, a, m); return x; }

bool check(ll x) {

	if(x<=Lim) return !np[x];

	if((x%2)==0 || (x%3)==0 || (x%5)==0 || (x%7)==0 || (x%11)==0 || (x%13)==0) return 0;

	int cnt=0; ll d=x-1; while(!(d&1)) d>>=1, ++cnt;

	for(int T=0; T<=50; ++T) {

		ll t=ipow(rand(2, x-1), d, x), pre=t;

		for(int i=1; i<=cnt; ++i, pre=t) {

			t=mul(t, t, x);

			if(t==1 && pre!=1 && pre!=x-1) return 0;

		}

		if(t!=1) return 0;

	}

	return 1;

}

void pre(ll n) {

	tot=0;

	int sq=sqrt(n+0.5)+1;

	for(int i=0; i<pcnt; ++i) {

		if(p[i]>sq) break;

		if(n%(p[i]-1)==0) {

			ll t=n/(p[i]-1);

			a[tot].p=p[i];

			while(t%p[i]==0)

				++a[tot].l, t/=p[i];

			++tot;

		}

	}

	for(int i=sq; i>=1; --i) if(n%i==0) {

		ll pr=n/i+1; if(pr<=sq) continue;

		if(check(pr))

			a[tot].p=pr, a[tot++].l=0;

	}

	// printf("tot:%d\n", tot);

	// for(int i=0; i<tot; ++i)

	//	printf("%lld ", a[i].p); puts("");

}

void dfs(int x, ll n, ll now) {

	if(n==1) {

		if(x==0) now*=2;

		b[ans++]=now;

		return;

	}

	if(x>=tot) return;

	dfs(x+1, n, now);

	ll pr=a[x].p;

	int l=a[x].l;

	if(n%(pr-1)) return;

	now*=pr;

	n/=pr-1;

	dfs(x+1, n, now);

	for(int j=0; j<l; ++j) {

		if(n%pr) break;

		now*=pr;

		n/=pr;

		dfs(x+1, n, now);

	}

}

void work(ll n) {

	ans=0;

	dfs(0, n, 1);

	printf("%d\n", ans);

	sort(b, b+ans);

	for(int i=0; i<ans; ++i)

		printf("%lld%c", b[i], " \n"[i==ans-1]);

}

int main() {

	int T; scanf("%d", &T);

	init();

	while(T--) {

		ll n;

		scanf("%lld", &n);

		if(n&1) {

			if(n==1) puts("2\n1 2");

			else puts("0");

			continue;

		}

		pre(n);

		work(n);

	}

	return 0;

}

巴特西

【BZOJ】3737: [Pa2013]Euler

题意：

分析

题解

最新文章

热门文章