【题目大意】

你有四个子任务：

1. 给定$a, b, c$，求方程$ax \equiv b (mod \quad c)$的最小非负整数解。

2. 给定$f, g, h$，求方程$g^x \equiv f (mod \quad h)$的最小非负整数解。

3. 给定$u, v, w$，求$x^u \equiv v (mod \quad w)$的在模意义下解的数量。

4. 给定$x, y, z$，求$(\phi(x)+\mu(y)) \quad mod \quad z$的值。

对于1~3任务中的数，均小于$2^{30}$，对于4任务中的数，均小于$2^{60}$。

【题解】

1. 扩展欧几里得

将式子化成$ax + ck = b$，用扩展欧几里得即可求出解。

2. BSGS：具体见这里。

3.

法一）求出$w$的原根$p$。设$p^b \equiv v (mod \quad w)$，而且$p^a \equiv x (mod \quad w)$，那么$p^{au} \equiv p^{b} (mod \quad w)$，由费马小定理（$a^{p-1} \equiv 1 (mod \quad p)$）得，解该方程等价于解$au \equiv b (mod \quad w-1)$，所以综合前两个问题即可。见代码solve3_1();

法二）借鉴二次剩余，那么设$y=gcd(u, w-1)$，那么如果$v^{\frac{w-1}{y}} \equiv 1 (mod \quad w)$，那么答案就是$y$，否则答案是$0$。

4. Pollard_Rho算法和Millar_Rabin算法的应用。

# include <stdio.h>
# include <iostream>
# include <stdlib.h>
# include <algorithm>
# include <time.h>
# include <math.h>
# include <map>
using namespace std;
typedef long long LL;
LL a, b, c;

inline LL ABS(LL a) {
	return a>0 ? a : -a;
}

// ============= SOLVE1 ================ //
// ax + by = c
LL x, y;
inline LL gcd(LL a, LL b) {
	if(b==0) return a;
	else return gcd(b, a%b);
}
inline LL exgcd(LL a, LL b) {
	if(b == 0) {
		x=1, y=0;
		return a;
	}
	LL ans = exgcd(b, a%b);
	LL tmp = x;
	x = y;
	y = tmp - a/b*y;
	return ans;
}
inline LL ex_gcd(LL a, LL b, LL c) {
	LL GCD=gcd(a, b);
	if(c%GCD != 0) return -1;
	LL del = c/GCD;
	exgcd(a, b);
	x = x * del;
	y = y * del;
	LL fc = b/GCD;
	x=(x%fc+fc)%fc;
	return x;
}

// ax + ck = b
inline void solve1(LL a, LL b, LL c) {
	LL gg = ex_gcd(a, c, b);
	if(gg != -1) cout << x << endl;
	else puts("-1");
}
// ============= SOLVE1 ================ //

inline LL mul(LL a, LL b, LL p) {
	// a*b mod p
	LL s=0;
	while(b) {
		if(b&1) s=(s+a)%p;
		a=a*2%p;
		b>>=1;
	}
	return s;
} 

inline LL inverse(LL a, LL b) {
    exgcd(a, b);
    if(x<0) x+=b;
    return x;
}


// ============= SOLVE2 ================ //

inline LL bsgs(LL A, LL B, LL C) {
	LL to = ceil(sqrt(C)), e=1;
	map<LL, LL> hash;
	hash.clear();
	hash[1] = to;
	for (LL i=1; i<to; ++i) {
		e=mul(e, A, C);
		if(!hash[e]) hash[e] = i;
	}
	e = mul(e, A, C);
	e = inverse(e, C);
	for (LL i=0; i<to; ++i) {
		if(hash[B]) {
			LL ret = hash[B];
			return i*to+(ret == to ? 0 : ret);
		}
		B = mul(B, e, C);
	}
	return -1;
}

inline LL ext_bsgs(LL a, LL b, LL c) {
	LL t, d=1, cnt=0;
	while(1LL != (t=gcd(a, c))) {
		if(b%t) return -1;
		b/=t, c/=t;
		d=d/t;
		mul(d, a, c);
		++cnt;
		if(d == b) return cnt;
	}
	b=b*inverse(d, c)%c;
	LL ret = bsgs(a, b, c);
	if(ret == -1) return -1;
	else return cnt + ret;
}

inline void solve2(LL a, LL b, LL c) {
	LL ans = ext_bsgs(b, a, c);
	cout << ans << endl;
}

// ============= SOLVE2 ================ //

inline LL power1(LL a, LL b, LL p) {
	LL s=1;
	while(b) {
		if(b&1) s=s*a%p;
		a=a*a%p;
		b>>=1;
	}
	return s;
}

inline LL power2(LL a, LL b, LL p) {
	LL s=1;
	while(b) {
		if(b&1) s=mul(s, a, p);
		a=mul(a, a, p);
		b>>=1;
	}
	return s;
}

// ============= SOLVE3 ================ //

LL ys[11000];
int ysn = 0;

inline LL getprrt(LL p) {
	if(p == 2) return 1;
	ysn = 0; LL tmp = p-1;
	for (LL i=2; i<=50000 && i*i <= tmp; ++i) {
		if(tmp % i == 0) {
			ys[++ysn] = (p-1)/i;
			do {tmp/=i;} while(tmp%i==0);
		}
	}
	if(tmp>1) ys[++ysn] = (p-1)/tmp;
	bool ok;
	int g = 1;
	while(1) {
		ok = 1; ++g;
		for (int i=1; i<=ysn; ++i)
			if(power1(g, ys[i], p) == 1) {
				ok = 0;
				break;
			}
		if(ok) return g;
	}
}

inline void solve3_1(LL a, LL b, LL c) {
	LL p, ans = 0;
	p = getprrt(c);
	LL g = bsgs(p, b, c);
	if(g == -1) ans = 0;
	else  {
		LL GCD=gcd(a, c-1);
		if(g%GCD != 0) ans = 0;
		else ans = GCD;
	}
	cout << ans << endl;
}

inline void solve3_2(LL a, LL b, LL c) {
	LL GCD = gcd(b, c-1);
	LL res = power2(a, (c-1)/GCD, c);
	if(res == 1LL) cout << GCD << endl;
	else cout << 0 << endl;
}

inline void solve3(LL a, LL b, LL c) {
	solve3_2(b, a, c);
}

// ============= SOLVE3 ================ //


// ============= SOLVE4 ================ //

const int Prime[13] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
const int N = 12;
inline bool witness(LL k, LL u, int pr, LL n) {
	LL powe = power2((LL)pr, u, n);
	if(powe == 1) return false;
	for (LL i=0; i<k; ++i) {
		if(powe == n-1) return false;
		if(powe == 1) return false;
		powe = mul(powe, powe, n);
	}
	return true;
}

inline bool MillarRabin(LL n) {
	for (int i=1; i<=N; ++i) {
		if(n == Prime[i]) return true;
		if(n%Prime[i] == 0) return false;
	}
	LL u = n-1, k = 0;
	while(!(u&1)) {
		++k;
		u>>=1;
	}
	for (int i=1; i<=N; ++i) 
		if(witness(k, u, Prime[i], n)) return false;
	return true;
}

inline void PollardRho(LL *pr, int& tot, LL x) {
	if(MillarRabin(x)) {
		pr[++tot] = x;
		return ;
	}
	LL a, b, c, del;
	srand(time(0));
	while(1) {
		c = rand()%x;
		a = b = rand()%x;
		b = (mul(b, b, x) + c) % x;
		while(a != b) {
			del = a-b;
			del = gcd(ABS(del), x);
			if(del > 1 && del < x) {
				PollardRho(pr, tot, del);
				PollardRho(pr, tot, x/del);
				return ;
			}
			a = (mul(a, a, x) + c) % x;	
			b = (mul(b, b, x) + c) % x;
			b = (mul(b, b, x) + c) % x;
		}
	}
}

inline LL phi(LL x) {
	if (x == 1) return 1;
	LL prime[120]; int tot=0;
	PollardRho(prime, tot, x);
	sort(prime+1, prime+tot+1);
	LL res = prime[1] - 1;
	for (int i=2; i<=tot; ++i) {
		if(prime[i] != prime[i-1]) res = res * (prime[i] - 1);
		else res = res * prime[i];
	}
	return res;
}

inline LL mu(LL x) {
	if(x == 1) return 1;
	LL prime[120]; int tot=0;
	PollardRho(prime, tot, x);
	sort(prime+1, prime+tot+1);
	LL res = -1;
	for (int i=2; i<=tot; ++i) {
		if(prime[i] != prime[i-1]) res = -res;
		else res = 0;
	}
	return res;
}

inline void solve4(LL a, LL b, LL c) {
	LL res1 = phi(a), res2 = mu(b);
	LL res = (res1+res2) % c;
	cout << res << endl;
}

// ============= SOLVE4 ================ //

int main() {
	freopen("super.in", "r", stdin);
	freopen("super.out", "w", stdout);
	cin >> a >> b >> c;
	solve1(a, b, c);
	cin >> a >> b >> c;
	solve2(a, b, c);
	cin >> a >> b >> c;
	solve3(a, b, c);
	cin >> a >> b >> c;
	solve4(a, b, c);
	return 0;
}