首页 > 代码库 > BZOJ 2219 数论之神 数论
BZOJ 2219 数论之神 数论
题目大意:求在[0,p)范围内的解的个数
鏼爷的题解:http://jcvb.is-programmer.com/posts/42036
我只是来粘代码的QAQ
指标啥的原根啥的中国剩余定理啥的真的完全不知道QAQ
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define INF static_cast<ll>(1e15) #define M 100100 using namespace std; typedef long long ll; typedef pair<ll,ll> abcd; namespace Hash_Set{ ll hash_table[M],val[M],tim[M],T; inline void Clear() { ++T; } ll Hash(ll x,ll v) { ll i; for(i=x%M;tim[i]==T;i++,i%=M) if(hash_table[i]==x) return val[i]; tim[i]=T;hash_table[i]=x; return val[i]=v; } } ll Quick_Power(ll x,ll y,ll p) { ll re=1; while(y) { if(y&1) re*=x,re%=p; x*=x,x%=p; y>>=1; } return re; } ll Get_Primitive_Root(ll p,ll phi_p) { static ll factors[500]; int i,j,tot=0; for(i=2;i*i<phi_p;i++) if(phi_p%i==0) factors[++tot]=i,factors[++tot]=phi_p/i; if(i*i==phi_p) factors[++tot]=i; for(i=2;i<p;i++) { for(j=1;j<=tot;j++) if(Quick_Power(i,factors[j],p)==1) break; if(j==tot+1) return i; } } ll GCD(ll x,ll y) { return y?GCD(y,x%y):x; } abcd EXGCD(ll x,ll y) { if(!y) return abcd(1,0); abcd temp=EXGCD(y,x%y); return abcd(temp.second,temp.first-x/y*temp.second); } ll EXBSGS(ll A,ll B,ll C) { ll i,A_m,D,m=static_cast<int>(ceil(sqrt(C))+1.0000001); Hash_Set::Clear(); for(i=0,A_m=1;i<m;i++,A_m*=A,A_m%=C) Hash_Set::Hash(A_m,i); for(i=0,D=1;i<=m;i++,D*=A_m,D%=C) { abcd temp=EXGCD(D,C); ll x=(temp.first*B%C+C)%C; ll re=Hash_Set::Hash(x,0); if(re) return i*m+re; } } ll Solve(ll a,ll b,ll p,ll d) { ll p_d=Quick_Power(p,d,INF); b%=p_d; if(!b) return Quick_Power(p,d-( (d-1)/a+1 ),INF); ll temp=0; while(b%p==0) b/=p,temp++; if(temp%a) return 0; d-=temp; ll phi=p_d-p_d/p,g=Get_Primitive_Root(p_d,phi); ll ind=EXBSGS(g,b,p_d); ll re=GCD(a,phi); if(ind%re) return 0; return re; } int main() { ll T,i; ll a,b,k,ans; #ifdef C_PoPoQQQ freopen("2219.in","r",stdin); freopen("2219.out","w",stdout); #endif for(cin>>T;T;T--) { #ifdef ONLINE_JUDGE scanf("%lld%lld%lld",&a,&b,&k); #else scanf("%I64d%I64d%I64d",&a,&b,&k); #endif k=k<<1|1;ans=1; for(i=2; i*i<=k && ans ;i++) if(k%i==0) { ll temp=0; while(k%i==0) k/=i,++temp; ans*=Solve(a,b,i,temp); } if( ans && k^1 ) ans*=Solve(a,b,k,1); #ifdef ONLINE_JUDGE printf("%lld\n",ans); #else printf("%I64d\n",ans); #endif } }
BZOJ 2219 数论之神 数论
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。