同余与模运算

2019-04-14 20:43发布

站内文章 / 模拟电子
9370 0 1603
发现自己还是看书少了，能从书上学到不少东西。 加减乘的模运算： #include 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 b,int n){ a %= n; b %= b; return (int)((a + b) % n); } int subtract_mod(int a,int b,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 #include 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
幂取模：输入a,n,m输出a^n mod m的值，a,n,m<=10^9 简单的代码，时间复杂度为O(n) int pow_mod(int a,int n,int m) { int ans=1; for(int i=0;i
下面可以利用分治法，减少时间复杂度。时间复杂度减少为O(logn) int pow_mod(int a,int n,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（三道杠）b(mod n)       ,a,b,n<=10^9 a和b关于模n同余，充要条件a-b是n的整数倍。 方程ax(三道杠)1(mod n)的解称为a关于模n的逆，当gcd(a,n)=1时，该方程组有唯一解，否则无解。 下面程序表示a(三道杠)1(mod n) 的解，要求gcd(a,n)=1 #include 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; }



热门文章