CINTA作业3. 编程题

CINTA 作业

Q1.GCD算法的迭代版本

#include <stdio.h>
#include <stdlib.h>
int main(){
    int a,b;
    scanf("%d %d",&a,&b);
    if(b > a){
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
    }
    while(b){
        int temp = b;
        b = a % b;
        a = temp; 
    }
    printf("gcd = %d",a);
    return 0;
}

Q2.验证EGCD算法的正确性

#include <stdio.h>
#include <stdlib.h>
int main(){
    int a,b;
    int r1 = 1;
    int r2 = 0;
    int s1 = 0;
    int s2 = 1;
    scanf("%d %d",&a,&b);
    if(b > a){
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
    }
    int a0 = a;
    int b0 = b;
    while(b){
        int temp = b;
        int q = a / b;
        b = a % b;
        int temp1 = r1;
        int temp2 = s1;
        r1 = r2;
        s1 = s2;
        r2 = temp1 - q * r1;
        s2 = temp2 - q * s1;
        a = temp; 
    }
    printf("gcd(%d,%d) = %d = %d * a + %d * b",a0,b0,a,r1,s1);
    return 0;
}

Q3. ax = b (mod N)，即给定整数a、b和N，求x

假设前提：x需要是整数，题目好像没提到....

思路：
* $a = N*y0 + r$
* $b = N * y1 + r$
* $a * x + N * y = b$
* 由裴蜀定理得 $a * x + N * y = b$ x,y为整数 <==> gcd(a,N) | b
* 由egcd可得一组解xr,yr
* $x = r * b /gcd(a,N) + N*k (k \in Z)$

#include <stdio.h>
#include <stdlib.h>
int egcd(int a,int b,int *r1,int *s1){
    int r2 = 0;
    int s2 = 1;
    if(b > a){
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
    }
    while(b){
        int temp = b;
        int q = a / b;
        b = a % b;
        int temp1 = *r1;
        int temp2 = *s1;
        r1 = &r2;
        s1 = &s2;
        r2 = temp1 - q * *r1;
        s2 = temp2 - q * *s1;
        a = temp; 
    }
    printf("gcd = %d\n",a);
    return a;
}
int main(){
    int a,b,n;
    scanf("%d %d %d",&a,&b,&n);
    int r1 = 1;
    int s1 = 0;
    printf("a = %d,b = %d,n = %d\n",a,b,n);
    int gcd = egcd(a,n,&r1,&s1);
    if(b % gcd){
        printf("No result.");
    }
    else {
        printf("x = %d + %d * k, k belongs to Integer",r1*b/gcd,n);
    }
    return 0;
}

Q4. ax = (1 mod N)，即给定整数a和N，求x

感觉就像是Q3的特殊情况

#include <stdio.h>
#include <stdlib.h>
int egcd(int a,int b,int *r1,int *s1){
    int r2 = 0;
    int s2 = 1;
    if(b > a){
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
    }
    while(b){
        int temp = b;
        int q = a / b;
        b = a % b;
        int temp1 = *r1;
        int temp2 = *s1;
        r1 = &r2;
        s1 = &s2;
        r2 = temp1 - q * *r1;
        s2 = temp2 - q * *s1;
        a = temp; 
    }
    printf("gcd = %d\n",a);
    return a;
}
int main(){
    int a,n;
    int b = 1;
    scanf("%d %d",&a,&n);
    int r1 = 1;
    int s1 = 0;
    printf("a = %d,b = %d,n = %d\n",a,b,n);
    int gcd = egcd(a,n,&r1,&s1);
    if(b % gcd){
        printf("No result.");
    }
    else {
        printf("x = %d + %d * k, k belongs to Integer",r1*b/gcd,n);
    }
    return 0;
}