求助!!!
查看原帖
求助!!!
215002
cncsy楼主2021/10/19 19:49

第二个点WA掉了

*思路:高精+快速幂求逆元

#include<bits/stdc++.h>
#define ll unsigned long long
#define p "19260817"
#define P 19260817
using namespace std;
template <typename T> void write(T x) {
    if (x < 0) x = -x, putchar('-');
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
    write(x);
    puts("");
}
string jianf(string s1,string s2)
{
	string st="";
	while(s1.size()<s2.size()) s1="00"+s1;
	while(s1.size()>s2.size()) s2="0"+s2;
	for(int i=s1.size()-1;i>=0;i--)
	{
		if(s1[i]<'0') s1[i-1]--,s1[i]+=10;
		int a=s1[i]-'0',b=s2[i]-'0';
		if(a<b) s1[i-1]--,a+=10;
		a-=b;
		st=char(a+'0')+st;
	}
	while(st[0]=='0') st.erase(0,1);
	return st;
}

bool cmp(string s1,string s2)
{
	if(s1.size()>s2.size()) return 1;
	if(s2.size()>s1.size()) return 0;
	if(s1>=s2) return 1;
	return 0;
}
string cf(string s1,string s2)
{
	string s3=s1,st="";
	s3=s1.substr(0,s2.size());
	if(s3<s2) s3=s3+s1[s2.size()];
	s1.erase(0,s3.size());
	while(1)
	{
		int a=0;
		while(cmp(s3,s2)){s3=jianf(s3,s2);a++;} 
		st=st+char(a+'0');
		if(s1=="" )break;
		while(!cmp(s3,s2)) s3=s3+s1[0],s1.erase(0,1);
	}
	if(s3=="") return "0";
	return s3;
}
int niyuan(ll x)
{
	ll k=x,p1=P-2,s=1;
	while(p1!=0)
	{
		k%=P;
		if(p1%2==1) s*=k;
		s%=P;
		p1=p1>>1;
		k=k*k;
	}
	return s;
}
int main()
{
	string s1="",s2="";
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) ;
	for(;isdigit(ch);ch=getchar()) s1=s1+ch;
	for(;!isdigit(ch);ch=getchar()) ;
	for(;isdigit(ch);ch=getchar()) s2=s2+ch;
	s1=cf(s1,p);
	s2=cf(s2,p);
	ll a,b;
	a=b=0;
	for(int i=0;i<s1.size();i++) a=a*10+s1[i]-'0';
	for(int i=0;i<s2.size();i++) b=b*10+s2[i]-'0';
	if(b==0)
	{
		puts("Angry!");
		return 0;
	}
	writeln((a*niyuan(b))%P);
    return 0;
}
2021/10/19 19:49
加载中...