其实是问一下关于exgcd
查看原帖
其实是问一下关于exgcd
696045
dyyyyyczyz楼主2023/7/8 02:52

最开始查了半天错,最后是翻了自己的同学 @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]就行了。 (我承认这块上课没听好好吧)

2023/7/8 02:52
加载中...