数据貌似神奇?
查看原帖
数据貌似神奇?
263469
Ink_Bottle楼主2020/9/13 12:11

RT,下载了一组数据,发现过了,但在介面却显示WA,这是为什么呢?

代码:

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
ll a,b,d,x,y,t,k,mod;
ll quick_pow(ll a,ll x,ll mod)
{
	ll t=1;
	while(x)
	{
		if(x&1) t=t*a%mod;
		a=a*a%mod;
		x>>=1;
	}
	return t;
}
void exgcd(ll a,ll b,ll &d,ll &x,ll &y)
{
	if(b==0)
	{
		d=a,x=1,y=0;
	}
	else
	{
		exgcd(b,a%b,d,x,y);
		int t=x;
		x=y;
		y=t-a/b*y;
	}
}
map<ll,ll> mapp;
ll BSGS(ll b,ll n,ll p)
{
	mapp.clear();
	ll m=ceil(sqrt(p));
	ll ttt=n%p;
	for(ll i=0;i<=m;i++)
	{
		mapp[ttt]=i;
		ttt=ttt*b%p;
	}
	ll tt,ans;
	tt=ttt=quick_pow(b,m,p);
	for(ll i=1;i<=m;i++)
	{
		if(mapp[tt])
		return cout << i*m-mapp[tt] << endl,0;
		tt=tt*ttt%p;
	}
	puts("Orz, I cannot find x!");
}
int main()
{
	cin >> t >> k;
	for(ll i=1;i<=t;i++)
	{
		cin >> a >> b >> mod;
		if(k==1) cout << quick_pow(a,b,mod) << endl;
		if(k==2)
		{
			exgcd(a,mod,d,x,y);
			if(b%d) puts("Orz, I cannot find x!");
			else
			{
				ll tt=mod/d;
                while(x<0) x+=tt;
                printf("%lld\n",((x*b/d)%tt+tt)%tt);
			}
		}
		if(k==3) BSGS(a,b,mod);
	}
	return 0;
}

输入:

10 3
937858122 885997939 782033017
1010346135 741625566 194852069
263534721 760033577 791950363
665446570 770180178 672211691
545831567 636973366 706065337
15908945 1039519602 1011976331
527454377 68336033 137591561
688499425 247312218 744102253
547721550 1017998378 610524181
82389719 851592955 793744117

输出:

Orz, I cannot find x!
37629763
163627719
182764719
106654163
52411945
Orz, I cannot find x!
Orz, I cannot find x!
Orz, I cannot find x!
12384086
2020/9/13 12:11
加载中...