3283: 运算器
Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 184 Solved: 59
[Submit][Status][Discuss]
Description
操作有3种：
Input
第一行一个正整数N，描述数据组数。
接下来的N行，每行4个正整数Sum，y，z，p。
Sum表述询问类型，如上题所述。对于第2种要求，若X不存在，则输出“Math Error”
Output
要求有N行输出，每行一个整数，为询问的答案。
Sample Input
4
1 2 10 1000
2 3 1 1000
2 2 3 4
3 2 7 9
1 2 10 1000
2 3 1 1000
2 2 3 4
3 2 7 9
Sample Output
24
0
Math Error
3
0
Math Error
3
HINT
操作1个数小于501。保证Y,Z,P小于10^9
操作2个数小于51 保证Y,Z,P小于10^9 P不一定为质数
操作3个数小于51 保证Y，Z小于10^9，P小于10^9
P不一定为质数
P<=10^9
假设分解质因数后,P=p1^s1*p2^s2*……保证pi^ki<=10^5
VFK上课时提到了这题，然后就试着做了一下。
本来还以为是水题，结果两个晚上就砸这道题上了，第一问不说了，为啥这类题第一问都是快速幂?第二问本以为可以用经典大步小步做，但是发现由于ax=b(mod c)当解得个数是gcd(a,c)，所以gcd(a,c)不等于1是复杂度可以卡到O(c)，于是我们可以考虑使gcd(a,c)==1，并且尽量不改变a^x=b (mod c)的解，我们想到了将gcd(a,c)中的因数消去，具体是不断找gcd(a,c)，然后借助 a=b (mod c) -> ak=bk (mod ck)的性质，设g=gcd(a,c),将原式变成a*a^(x-1)=b (mod c)，发现有解仅当g|a&&g|b&&g|c，同时消去因子，直到互质，这里要特殊处理x较小的解。
第三问方法是由p是质数的快速阶乘修改而来，这类题通常将p写成PI(pi^ki)的形式，分别计算，在套用中国剩余定理。计算ans=n! mod p [p=pp^pk]，将ans表示为k*pp^b的形式。考虑将n!中的数分为与p互质的数，与p不互质的数，对于第一类，由于[1,n),[n+1,2*n)结果相同，可用快速幂优化，对于第二类，同时除以pp可转化为规模n/pp的子问题。
这道题告诉我以后数论题千万不要用pair存值，稍有修改，一定免不了使用pair<pair<int,int> ,int>这类奇葩类型。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<set>
#include<cmath>
#include<vector>
using namespace std;
#define MAXN 1001000
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
typedef long long qword;
bool pflag[MAXN];
int prime[MAXN],topp=-;
void init()
{
for (int i=;i<MAXN;i++)
{
if (!pflag[i])
prime[++topp]=i;
for (int j=;j<=topp && i*prime[j]<MAXN;j++)
{
pflag[i*prime[j]]=true;
if (i%prime[j]==)break;
}
}
}
qword fact[MAXN];
qword pow_mod(qword x,qword y,qword mod)
{
qword ret=;
while (y)
{
if (y&)
ret=ret*x%mod;
x=x*x%mod;
y>>=;
}
return ret;
}
qword gcd(qword x,qword y)
{
return x%y==?y:gcd(y,x%y);
}
qword extgcd(qword p,qword q,qword &x,qword &y)
{
if (!q)
{
x=;y=;
return p;
}
qword xx,yy;
qword ret=extgcd(q,p%q,xx,yy);
x=yy;
y=xx-p/q*yy;
return ret;
} pair<int,int> lst[MAXN];
int topl=-;
qword BabyStepGiantStep_Naive(qword k,qword a,qword b,int p)//k*a^x==b (mod p) (gcd(a,p)==1)
{
qword res=INFL;
int sb=(int)ceil(sqrt(p));
qword x=k;
topl=-;
for (int i=;i<sb;i++)
{
lst[++topl].first=(int)x;
lst[topl].second=i;
x=x*a%p;
}
sort(lst,lst+topl+);
qword y=pow_mod(a,sb,p);
x=;
qword xx,yy;
qword r;
for (int i=;i<sb;i++)
{
r=extgcd(x,p,xx,yy);
if (b%r==)
{
xx*=b/r;
xx=(xx%(p/r)+p/r)%(p/r);
if (lower_bound(lst,lst+topl+,make_pair((int)xx,-INF))->first==xx)
{
res=i*sb+lower_bound(lst,lst+topl+,make_pair((int)xx,-INF))->second;
break;
}
}
x=x*y%p;
}
if (res==INFL)
return -;
else
return res;
}
void BabyStepGiantStep(qword a,qword b,int p)//a^x==b (mod P)
{
qword x=%p;
for (int i=;i<;i++)
{
if (x==b)
{
printf("%d\n",i);
return ;
}
x=x*a%p;
}
int delta=;
int g;
qword kk=;
while ((g=(int)gcd(a,p))!=)
{
if (b%g)
{
printf("Math Error\n");
return ;
}
kk*=a/g;
delta++;
b/=g;
p/=g;
kk%=p;
}
qword res=BabyStepGiantStep_Naive(kk,a,b,p);
if (res==-)
printf("Math Error\n");
else
printf("%d\n",(int)(res+delta));
}
void init_fact(int p,int pp)
{
fact[]=;
for (int i=;i<=p;i++)
{
if (i%pp)
{
fact[i]=fact[i-]*i%p;
}
else
{
fact[i]=fact[i-];
int x=i;
while (x%pp==)
{
x/=pp;
}
}
}
}
pair<qword,int> solve2(int n,int p,int pp,int pk)//n! mod p (p=pp^k)
{
pair<qword,int> res;
if (!n)return make_pair(,);
pair<qword,int> pr=solve2(n/pp,p,pp,pk);
res.first=pow_mod(fact[p-],n/p,p) * fact[n%p]%p * pr.first%p;
res.second=n/pp + pr.second;
return res;
}
qword solve4(vector<pair<pair<int,int>,int> > &lst)
{
qword mm=;
for (int i=;i<lst.size();i++)
mm=mm*lst[i].first.first;
qword ans=;
for (int i=;i<lst.size();i++)
{
ans+=mm/lst[i].first.first*pow_mod(mm/lst[i].first.first%lst[i].first.first,lst[i].first.second-,lst[i].first.first)%mm*lst[i].second%mm;
ans%=mm;
}
return ans;
}
int factor[MAXN][];
int totf=;
void solve3(int n,int m,int p)//n!/(m!(n-m)!) mod p
{
if (n<m)
{
printf("0\n");
return ;
}
qword x=p;
totf=;
for (int i=;i<=topp;i++)
{
if (x%prime[i]==)
{
x/=prime[i];
factor[totf][]=prime[i];
factor[totf][]=prime[i];
factor[totf][]=prime[i]-;
factor[totf][]=;
while (x%prime[i]==)
{
factor[totf][]*=prime[i];
factor[totf][]*=prime[i];
factor[totf][]++;
x/=prime[i];
}
totf++;
}
}
if (x!=)
throw ;
vector<pair<pair<int,int>,int> > lst;
pair<qword,qword> pr,res;
for (int i=;i<totf;i++)
{
init_fact(factor[i][],factor[i][]);
res=solve2(n,factor[i][],factor[i][],factor[i][]);
pr=solve2(m,factor[i][],factor[i][],factor[i][]);
pr.first=pow_mod(pr.first,factor[i][]-,factor[i][]);pr.second=-pr.second;
res.first=res.first*pr.first%factor[i][];
res.second=res.second+pr.second;
pr=solve2(n-m,factor[i][],factor[i][],factor[i][]);
pr.first=pow_mod(pr.first,factor[i][]-,factor[i][]);pr.second=-pr.second;
res.first=res.first*pr.first%factor[i][];
res.second=res.second+pr.second;
res.first=res.first*pow_mod(factor[i][],res.second,factor[i][])%factor[i][];
lst.push_back(make_pair(make_pair(factor[i][],factor[i][]),res.first));
}
qword ans;
ans=solve4(lst);
printf("%d\n",(int)ans);
} int main()
{
freopen("input.txt","r",stdin);
int n,m,x,y,z;
scanf("%d",&n);
int opt;
init();
for (int i=;i<=n;i++)
{
scanf("%d%d%d%d",&opt,&x,&y,&z);
if (opt==)
{
printf("%d\n",(int)pow_mod(x,y,z));
}else if (opt==)
{
BabyStepGiantStep(x,y,z);
}else if (opt==)
{
solve3(y,x,z);
}
}
}