BZOJ 2219: 数论之神

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=2219

N次剩余+CRT。。。

就是各种奇怪的分类讨论。。

#include<cstring>
#include<iostream>
#include<cstdio>
#include<map>
#include<cmath>
#include<algorithm>
#define rep(i,l,r) for (int i=l;i<=r;i++)
#define down(i,l,r) for (int i=l;i>=r;i--)
#define clr(x,y) memset(x,y,sizeof(x))
#define maxn 50050
#define inf 2000000000
using namespace std;
int a,b,k,p,t,ans;
map<int,int> mp;
int read(){
int x=,f=; char ch=getchar();
while (!isdigit(ch)) {if (ch=='-') f=-; ch=getchar();}
while (isdigit(ch)) {x=x*+ch-''; ch=getchar();}
return x*f;
}
int Pow(int x,int y){
int ans=;
while (y){
if (y&) ans=1LL*ans*x;
x=1LL*x*x; y>>=;
}
return ans;
}
int Pow(int x,int y,int mo){
int ans=; while (y){
if (y&) ans=1LL*ans*x%mo;
x=1LL*x*x%mo; y>>=;
}
return ans;
}
int divs[maxn],dtot;
int groot(int p){//是对于p-1的每一个素因子a去检查(p-1)/a!!
dtot=;
int q=p-;
for (int i=;i*i<=q;i++){
if (q%i==) {
divs[++dtot]=i;
if (i*i!=q) divs[++dtot]=q/i;
}
}
for (int i=;i<p;i++){
int ok=;
rep(j,,dtot) if (Pow(i,divs[j],p)==) {ok=;break;}
if (!ok) return i;
}
}
int exgcd(int a,int b,int &x,int &y){
if (b==) {
x=; y=; return a;
}
int d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int gcd(int a,int b){
if (b==) return a;
return gcd(b,a%b);
}
int NI(int a,int b){
int x,y;
exgcd(a,b,x,y);
return (x%b+b)%b;
}
int bsgs(int a,int b,int p){
mp.clear();
int m=sqrt(p)+,mul,tmp;
int now=; rep(i,,m-) {if (!mp.count(now)) mp[now]=i; now=1LL*now*a%p;}
now=; mul=Pow(a,m,p);
rep(i,,m-){
tmp=1LL*b*NI(now,p)%p;
if (mp.count(tmp)) return mp[tmp]+i*m;
now=1LL*now*mul%p;
if (now==) break;
}
return inf;
}
int solve(int a,int b,int p,int d){
int pd=Pow(p,d);
b=b%pd;
if (b==) return Pow(p,d-((d-)/a+));
else {
int bet=;
while (b%p==) bet++,b/=p;
if (bet%a!=) return ;
int tt=bet/a;
int g=groot(p),phi=pd-pd/p;
int ind=bsgs(g,b,pd);
int d=gcd(a,phi);
if (ind%d==) return d*Pow(p,(a-)*tt);
else return ;
}
}
int main(){
t=read();
while (t--){
a=read(); b=read(); k=read();
p=*k+;
ans=;
for (int i=;i*i<=p&&ans;i++) if ((p%i)==) {
int now=; while ((p%i)==) p/=i,now++;
ans=ans*solve(a,b,i,now);
}
if (p!=&&ans) ans=ans*solve(a,b,p,);
printf("%d\n",ans);
}
return ;
}
上一篇:spring 命名空间


下一篇:面试知识点准备-C++常见问题