同餘與模運算

發現自己還是看書少了，能從書上學到不少東西。

加減乘的模運算：

#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 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<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\n",ans);
    }
    return 0;
}      

幂取模：輸入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<n;i++) ans=(int)((long long)ans*n%m);
}      

下面可以利用分治法，減少時間複雜度。時間複雜度減少為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<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\n",(1+n*y)/a);
            break;
        }
    }


    return 0;
}