同余与模算术

1.大整数取模

把大整数写成“自左向右”的形式：1234=（(1*10+2)*10+3)*10+4;然后逐步取模。

eg：n<=10¹⁰⁰,m<=10¹⁸。但是要注意乘法溢出的问题。

代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
char a[200];
long long p;
while(cin>>a>>p)
{
int len=strlen(a);
int ans=0;
for(int i=0;i<len;i++)
ans=(ans*10+a[i]-'0')%p;
cout<<ans<<endl;
}
return 0;
}

为了解决上面乘法溢出的问题，可以采用如下方法：

2.F快速幂

大致意思是给出三个数n，m，p。他们的范围是0到10¹⁸。

求n*m%p。

代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
long long n,m,p;
while(cin>>n>>m>>p)
{
n%=p;
long long ans=0;
while(n)
{
if(n&1)//判断最低位是否为1
ans=(ans+m)%p;
n/=2;
m=2*m%p;
}
cout<<ans<<endl;
}
return 0;
}

3.T快速幂（幂取模）

输入正整数a，n，m，输出 aⁿ mod m 的值。a，n，m<=10¹⁸ 。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll pow_mod(ll a,ll n,ll m)
{
if(n==0)
return 1;
ll
x=pow_mod(a,n/2,m);
ll ans=x*x%m;
if(n&1)
ans=ans*a%m;
return ans;
}
int main()
{
ll a,n,m;
while(cin>>a>>n>>m)
{
cout<<pow_mod(a,n,m)<<endl;
}
return 0;
}

或者

ll pow_mod(ll a,ll b,int n)
{
a%=n;
ll ans=1;
while(b)
{
if(b&1)
ans=ans*a%n;
b=b>>1;
a=a*a%n;
}
return ans;
}

Last but not lest,

模线性方程组

输入正整数a，b，n解方程ax≡b(mod n)。a，b，n<=10⁹ 。

拓展:同于模定理：a≡b(mod n)的意思是：a和b除以n的余数相同。其次充要条件是a-b是n的整数倍。

     这样，这个倍数是有，那么ax-b=ny，移项，ax-ny=b。这个时候就用扩展欧几里德算法自己叭叭叭敲吧。

提示：

 

typedef unsigned long long ll;//要是觉得long long 敲起来太长可以这样

 

 

 

今天也是元气满满的一天！good luck！