Gym 102055K Mr. Panda and Kakin（欧拉定理降幂 + O(1)快速乘

题意

给定 $n$n, $c$c (n,c<1e18)
其中 $n$n 是两个相邻素数的乘积
求 $x^{2^{30}+3}\equiv c\left(modn\right)$x230+3≡c (mod n) 的解 $x$x

分析

首先将 $n$n 进行分解，因为素数相邻，所以从 $\sqrt{n}$n ​ 开始遍历，得 $n=p\ast q$n=p∗q
由积性函数
$\phi \left(n\right)=(p-1)(q-1)$φ(n)=(p−1)(q−1)
令 $t=2^{30}+3$t=230+3
因为 $t$t 是质数，所以
$x^t\equiv x^{tmod\phi \left(n\right)}\left(modn\right)$xt≡xt mod φ(n) (mod n)
$t$t 关于 $\phi \left(n\right)$φ(n) 的逆存在，记为 $t^{-1}$t−1，可以用 $exgcd$exgcd 求出
于是 $x\equiv x^{t{t}^{-1}}\equiv c^{t^{-1}}\left(modn\right)$x≡xtt−1≡ct−1 (mod n)
所以只要求出
$c^{t^{-1}}modn$ct−1 mod n即可
不过由于 $c,n$c,n 都是 $longlong$long long 范围，溢出时取模会发生错误，于是用
$O\left(1\right)$O(1) 快速乘来解决这个问题
由于取余运算实现如下：
$abmodp=ab-\lfloor \frac{ab}{p}\rfloor \ast p$ab mod p=ab−⌊pab​⌋∗p
我们只要保证差值是正确得即可，于是让两个同时溢出，就能保证差值是正确的
代码如下：

//t = a * b % p
LL mul(LL a, LL b, LL p){
	LD x;
	x = LD(a) / p * b;
	return ((a * b - x * p) % p + p) % p
} 

这样子问题就解决了

总代码如下

#include <bits/stdc++.h>
using namespace std;
typedef long double LD;
typedef long long LL;
LL n, c, p, q, t, x, y, w = (1 << 30) + 3;
void exgcd(LL a, LL b, LL &x, LL &y){
	if(!b) x = 1, y = 0;
	else{
		exgcd(b, a % b, y, x);
		y -= a / b * x;
	}
}
LL mul(LL a, LL b, LL p){
	LD x;
	return ((a * b - LL(LD(a) / p * b) * p) % p + p) % p;
}
LL ksm(LL a, LL b, LL p){
	LL s = 1;
	while(b){
		if(b % 2) s = mul(s, a, p);
		a = mul(a, a, p);
		b /= 2;
	}
	return s;
}
int main(){
	int i, j, m, T, tt;
	scanf("%d", &T);
	for(tt = 1; tt <= T; tt++){
		scanf("%lld%lld", &n, &c);
		for(i = sqrt(n); i; i--){
			if(n % i == 0){
				p = i;
				q = n / i;
				break;
			}
		}
		t = (p - 1) * (q - 1);
		//return 0;
		exgcd(w, t, x, y);
		x = (x % t + t) % t;
		printf("Case %d: ", tt);
		printf("%lld\n", ksm(c, x, n));
	}
	return 0;
}