扩展CRT +扩展LUCAS

再次感谢ｚｙｆ２０００超强的讲解。

扩展CRT其实就是爆推式子，然后一路合并，只是最后一个式子上我有点小疑惑，但整体还算好理解。

#include<iostream>

#include<cstdio>

#include<queue>

#include<map>

#include<algorithm>

#include<vector>

#include<bitset>

#include<set>

#include<cstring>

#include<string>

#define ll long long

#define pb push_back

#define _mp make_pair

#define db double

#define eps 1e-9

#define inf 1e9

using namespace std;

const int maxn=1e5+7;

const int maxm=100005;

const int mod=1e9+7;

inline ll read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

ll x,y;

ll m[maxn],c[maxn];

ll gcd(ll x,ll y)

{

	return y==0?x:gcd(y,x%y);

}

void exgcd(ll a,ll b,ll &x,ll &y)

{

	if(b==0)

	{

		x=1;y=0;return;

	}

	exgcd(b,a%b,y,x);

	y-=a/b*x;

	return;

}

ll inv(ll a,ll b)

{

	exgcd(a,b,x,y);

	x=(x%b+b)%b;

	if(!x)x+=b;

	return x;

}

int main()

{

	int t;

	while(~scanf("%d",&t))

	{

		for(int i=1;i<=t;i++)

		{

			m[i]=read();c[i]=read();

		}

		int flag=1;

		for(int i=2;i<=t;i++)

		{

			ll m1=m[i-1],m2=m[i],c1=c[i-1],c2=c[i];

			ll tt=gcd(m1,m2);

			if((c2-c1)%tt!=0)

			{

				flag=0;

				break;

			}

			m[i]=m1*m2/tt;

			c[i]=inv(m1/tt,m2/tt)*(c2-c1)/tt%(m2/tt)*m1+c1;

			c[i]=(c[i]%m[i]+m[i])%m[i];

		}

		if(!flag)cout<<"-1\n";

		else cout<<c[t]<<"\n";

	}

}

　扩展LUCAS里面涉及的东西就比较多了，首先质因数分解转换为一个同余模方程，然后将阶乘中的ｐｉ的因子拿掉算一算，最后再加回来，最后显然可以按照ＣＲＴ去合并，看博客看得懂，不过想为什么就比较难了，要注意有ｐｋ的循环节，然后会有没有算的部分要暴力枚举（就是循环节之外的那几个数），因为不一定是整除的。PS：这个模板题我因为ｒｅａｄ（）写错导致了ＷＡ了一小时，改的和别人一模一样都是WA，然后仔细读了一下发现ｒｅａｄ（）里的ｘ必须写ｌｌ。。。。。我真是个智障。

#include<iostream>

#include<cstdio>

#include<queue>

#include<map>

#include<algorithm>

#include<vector>

#include<bitset>

#include<set>

#include<cstring>

#include<string>

#define ll long long

#define pb push_back

#define _mp make_pair

#define db double

using namespace std;

const int maxn=1e5+7;

const int maxm=100005;

inline ll read()

{

    ll x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

ll x,y,ans,n,m;

ll Mod;

ll q_pow(ll a,ll p,ll mod)

{

    ll ans=1LL;

    for (;p;p>>=1,a=a*a%mod)

        if (p&1)

            ans=ans*a%mod;

    return ans;

}

void exgcd(ll a,ll b,ll &x,ll &y)

{

	if(b==0)

	{

		x=1ll;y=0ll;return;

	}

	exgcd(b,a%b,y,x);

	y-=a/b*x;

}

ll inv(ll a,ll b)

{

	if(!a)return 0ll;

	//ll a=A,b=t,x=0ll,y=0ll;

	//cout<<b<<" ";

	x=0ll,y=0ll;

	exgcd(a,b,x,y);

	//cout<<b<<endl;

	x=((x%b)+b)%b;

	if(!x)x+=b;

	return x;

}

ll mul(ll n,ll pi,ll pk)

{

	if(!n)return 1ll;

	ll ans=1ll;

	if(n/pk)

	{

		for(ll i=2;i<=pk;i++)

		{

			if(i%pi)ans=ans*i%pk;

		}

		ans=q_pow(ans,n/pk,pk);

	}

	for(ll i=2;i<=n%pk;i++)

	{

		if(i%pi)ans=ans*i%pk;

	}

	return ans*mul(n/pi,pi,pk)%pk;

}

ll c(ll n,ll m,ll pi,ll pk)

{

	if(m>n)return 0ll;

	ll a=mul(n,pi,pk),b=mul(m,pi,pk),c=mul(n-m,pi,pk);

	ll cnt=0ll,ans;

	for(ll i=n;i;i/=pi)cnt+=i/pi;

	for(ll i=m;i;i/=pi)cnt-=i/pi;

	for(ll i=n-m;i;i/=pi)cnt-=i/pi;

	ans=a*inv(b,pk)%pk*inv(c,pk)%pk*q_pow(pi,cnt,pk)%pk;

	return ans*(Mod/pk)%Mod*inv(Mod/pk,pk)%Mod;

}

int main()

{

	n=read();m=read();Mod=read();

	ll tt=Mod;

	for(ll i=2;i<=Mod;i++)

	{

		if(tt%i==0)

		{

			ll ps=1ll;

			while(tt%i==0)tt/=i,ps*=i;

			ans=(ans+c(n,m,i,ps))%Mod;

		}

	}

	cout<<ans<<"\n";

}

　然后CRT、LUCAS的代码就不贴了，反正众所周知，做完模板题一般是没什么用的，所以做题的时候就会看到他们了。

巴特西

扩展CRT +扩展LUCAS

最新文章

热门文章