首页 > itarticle > yusijia’s blog 题目 1

yusijia’s blog 题目 1

admin 11月 12, 2020 0

Contents

题目：

输入n，2的x次方%n=1，求x，如果无解输出-1，x属于正整数。

分析：如果n为偶数则无解
2^x % n = 1等价于2^x = 1 (mod n);




int ()
{
    int n, x, ans;
    while(scanf("%d", &n) != EOF){
        if(n % 2 == 0){
            printf("-1n");
            continue;
        }
        ans = 1;
        for(x = 1; ; x++){
            ans = (ans * 2) % n;
            if(ans == 1){
                printf("%dn", x);
                break;
            }
        }
    }
    return 0;
}