最开始查了半天错,最后是翻了自己的同学 @Eureka_yzy (如果真引过来了的话没你的事)发的帖子意外发现是exgcd写错了,改了之后20分到60分。(已删除不必要的注释和谜之无用代码)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,k;
ll a[11],b[11];
ll m=1,mi[11];
ll t[11];
//void ksm(int x,int y,int i)
///{
// int ans=1,c=y-2,ti=x;
// while (c)
// {
// if (c&1)
// {
// ans=ans*ti%y;
// }
// ti=ti*ti%y;
// c>>=1;
/// }
// t[i]=ans;
//}
void exgcd(ll s,ll z,ll &x,ll &y)
{
if (z==0)
{
x=1;
y=0;
return ;
}
exgcd(z,s%z,x,y);
ll k=x;
x=y;
y=k-y*(s/z);
}
int main()
{
ll ans=0;
ll i;
cin>>n;
for (i=1;i<=n;i++)
{
cin>>a[i]>>b[i];
m=m*a[i];
}
for (i=1;i<=n;i++)
{
mi[i]=m/a[i];
//ksm(mi[i],a[i],i);
exgcd(mi[i],a[i],t[i],k);
ans+=t[i]*mi[i]*b[i];
}
cout<<ans%m;
return 0;
}
之后调试发现exgcd出来有负数,刚开始以为是正负搞反了加了个绝对值没有用,最后还是翻了帖子改成了这样100分。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,k;
ll a[11],b[11];
ll m=1,mi[11];
ll t[11];
//void ksm(int x,int y,int i)
///{
// int ans=1,c=y-2,ti=x;
// while (c)
// {
// if (c&1)
// {
// ans=ans*ti%y;
// }
// ti=ti*ti%y;
// c>>=1;
/// }
// t[i]=ans;
//}
void exgcd(ll s,ll z,ll &x,ll &y)
{
if (z==0)
{
x=1;
y=0;
return ;
}
exgcd(z,s%z,x,y);
ll k1=x;
x=y;
y=k1-y*(s/z);
}
int main()
{
ll ans=0;
ll i;
cin>>n;
for (i=1;i<=n;i++)
{
cin>>a[i]>>b[i];
m=m*a[i];
}
for (i=1;i<=n;i++)
{
mi[i]=m/a[i];
//ksm(mi[i],a[i],i);
exgcd(mi[i],a[i],t[i],k);
if (t[i]>0)
ans+=t[i]*mi[i]*b[i];
else ans+=(t[i]+a[i])*mi[i]*b[i];
}
cout<<ans%m;
return 0;
}
其实不理解为什么exgcd求出来会有负的,还有为什么改成t[i]+a[i]就行了。 (我承认这块上课没听好好吧)