2870 - 【验证型】第11章：指针和数组 2^? mod = 1
时间限制 : 1 秒
内存限制 : 20 MB
给你一个正整数n，要求你找到最小的x（x>0）满足2^x mod n = 1。
题目输入
第一行输入N，表示测试数据的组数，接下来N行输入测试数据n。
题目输出
如果最小的x存在，则输出2^x mod n = 1（注意x和n要用具体的值代替），否则输出2^? mod n = 1，若x > 99998也只需输出 2^? mod n = 1。
输入/输出样例
输入格式
2 2 5
输出格式
2^? mod 2 = 1 2^4 mod 5 = 1
C语言解答
#include<stdio.h> #include<math.h> #include<stdlib.h> int main() { int n; scanf("%d", &n); int nTwo; int j; int *a = (int *)malloc(n*sizeof(int)); int *x = (int *)malloc(n*sizeof(int)); int i; for(i = 0; i < n; i++) { scanf("%d", &a[i]); } for(i = 0; i < n; i++) { if(a[i] == 1) { x[i] = 1; continue; } if(!(a[i]%2)) { x[i] = 0; continue; } for(j = 2; j < 99999; j++) { nTwo = pow(2, j); if(nTwo % a[i] == 1) { x[i] = j; break; } } } for(i = 0; i < n; i++) { if(!x[i]) { printf("2^? mod %d = 1\n", a[i]); } else { printf("2^%d mod %d = 1\n", x[i], a[i]); } } return 0; }