对于数论的学习比较的碎片化，所以开了一篇随笔来记录一下学习中遇到的一些坑，主要通过题目来讲解
本题围绕：积与余数
HDU1395 2^x mod n = 1
题目描述
输入一个数n，如果存在2的x次方mod输出的n余数为1，则输出2^x mod n = 1，否则输出2^? mod n = 1，其中n替换为每次输出的n的具体数值
输入
正整数n，读取到文件尾
输出
2^x mod n = 1或者2^? mod n = 1
样例输入
2
5
样例输出
2^? mod 2 = 1
2^4 mod 5 = 1
题目分析
对于本题，要注意的点有：首先对于x的范围题目是没有给出的，所以不能想当然的假设把2^x设定在int或者long long的范围内用空间换时间的方法去做（对不起我踩坑了），再者，对于本题有一个概念性的知识点：多个数的积取余数等于这几个数分别取余数后的积的余数（几个数积的余数等于这几个数的余数的积的余数），这个概念可以使我们对一些情况进行优化，使得在计算很大的数的余数的时候不会溢出
代码：
#include<iostream>
#include<stdio.h>
using namespace std; int main(){
int n;
while(scanf("%d", &n) != EOF){
if(n == || n % == ) printf("2^? mod %d = 1\n", n); //偶数mod偶数余数不可能为1 任何数mod1 == 0
else{
int x = ;
int ans = ;
while(true){ //每次都将x * 2，然后对于x mod n（几个数积的余数等于这几个数余数的积的余数）
x *= ; //这样使得在数很大的时候不会溢出
ans++;
if(x % n == ){
printf("2^%d mod %d = 1\n", ans, n);
break;
}else{
x %= n;
}
}
}
}
return ;
}