同余与模运算
发布时间：2020-12-13 20:46:09 所属栏目：PHP教程 来源：网络整理
导读：发现自己还是看书少了，能从书上学到很多东西。 加减乘的模运算： #includecstdiousing namespace std;int mul_mod(int a,int b,int n){ a %= n; b %= b; return (int)((long long)a * b % n);}///如果n本身超int，就要用高精度了int add_mod(int a,int n){
|
发现自己还是看书少了，能从书上学到很多东西。 加减乘的模运算： #include<cstdio>
using namespace std;
int mul_mod(int a,int b,int n){
a %= n; b %= b;
return (int)((long long)a * b % n);
}///如果n本身超int，就要用高精度了
int add_mod(int a,int n){
a %= n; b %= b;
return (int)((a + b) % n);
}
int subtract_mod(int a,int n){
a %= n; b %= b;
return (int)((a - b + n) % n);
}
int main()
{
return 0;
} 大整数取模：也就是从头到尾，每当数到达大于等于n就对n取模，相当于把大整数转换成1234 = ((1*10+2)*10+3)*10+4的情势 输入大整数，和n #include<cstdio>
#include<cstring>
using namespace std;
int main()
{
int m;
char n[100];
scanf("%s%d",n,&m);
int len=strlen(n);
int ans=0;
for(int i=0;i<len;i++){
ans=(int)(((long long)ans*10 + n[i] - '0')%m );
printf("%d
",ans);
}
return 0;
}
幂取模：输入a,m输出a^n mod m的值，a,m<=10^9 简单的代码，时间复杂度为O(n) int pow_mod(int a,int n,int m)
{
int ans=1;
for(int i=0;i<n;i++) ans=(int)((long long)ans*n%m);
} 下面可以利用分治法，减少时间复杂度。时间复杂度减少为O(logn) int pow_mod(int a,int m)
{
if(n==0) return 1;
int x=pow_mod(a,n/2,m);
long long ans=(long long)x*x%m;
if(n%2==1) ans=ans*a%m;
return (int)ans;
} a^29=(a^14)^2*a,a^14=(a^7),a^3=a^2*a a=1*1*a;
摹拟线性方程组：输入a,b,c解方程 ax（3道杠）b(mod n) ,a,n<=10^9 a和b关于模n同余，充要条件a-b是n的整数倍。 方程ax(3道杠)1(mod n)的解称为a关于模n的逆，当gcd(a,n)=1时，该方程组有唯1解，否则无解。 下面程序表示a(3道杠)1(mod n) 的解，要求gcd(a,n)=1 #include<cstdio>
using namespace std;
int main()
{
int a,n;
scanf("%d%d",&a,&n);
int x;
for(int y=0;;y++)
{
if( (1+n*y)%a==0 ){
printf("x = %d
",(1+n*y)/a);
break;
}
}
return 0;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |