题目描述
LSZ很皮！LSZ的皮肤衣更皮！
LSZ有很多件神奇的皮肤衣，而且LSZ总是喜欢一次穿上多件皮肤衣（一件套一件，而且一直穿好多天），这些皮肤衣有透明或不透明两种状态，当不透明的皮肤衣吸收了一天的阳光直射后，就会变成透明的皮肤衣，透明的皮肤衣能使阳光照射到里层皮肤衣，而透明的皮肤衣再吸收阳光，会在第二天会变成不透明的皮肤衣，不透明的皮肤衣会阻止阳光照射到里层皮肤衣。
LSZ从某天起（该天算作第1天）穿上N件皮肤衣（刚开始所有皮肤衣都是不透明的），问你最少要经过多少天，LSZ身上的皮肤衣都经历过透明变化？
例如今天（公元2018年6月17日）LSZ穿了3件皮肤衣服，会在公元2018年6月21日3件皮肤衣都会经历过透明变化。
输入格式
一行，只有一个整数N。
输出格式
最少的天数（对N取余数）
样例
样例输入1
3
样例输出1
2
样例1解释
使用0代表皮肤衣透明状态。
使用1代表皮肤衣不透明的状态。
5对3取余数为2。
样例输入2
5
样例输出2
2
思路分析
这题显然是要找规律，经过大量打表，发现答案满足一个公式：
(2^(n-1)+1)mod(n)
当然这种指数极的东西直接暴力会爆掉，就需要用到快速幂：
-
快速幂算法详解：
原理：
以下以求a的b次方来介绍 [1]
把b转换成二进制数。
该二进制数第i位的权为
例如
11的二进制是1011
因此，我们将a¹¹转化为算
关键操作：
b & 1//取b二进制的最低位，判断和1是否相同，相同返回1，否则返回0，可用于判断奇偶 b>>1//把b的二进制右移一位，即去掉其二进制位的最低位板子：
#include<bits/stdc++.h> using namespace std; long long quickpower(long long x,long long y){ long long ans=1,cnt=x; while(y){ if(y&1){ //判断y的最低位是否为1 ans*=cnt; //为1就将ans乘上对应的x的cnt次方 } cnt*=cnt;//每次y的二进制右移一位都要将cnt平方，以便下一位计算用 y>>=1; } return ans; } int main(){ long long x,y,ans; cin>>x>>y; ans=quickpower(x,y); cout<<ans; return 0; }以上参考了[百度百科][https://baike.baidu.com/item/快速幂/5500243?fr=aladdin]
代码实现
#include <iostream>
#include <cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
ll power(ll x,ll y,ll mod){
ll ans = 1,cnt = x;
while(y){
if(y&1){
ans = (ans*cnt)%mod;
}
cnt = (cnt*cnt)%mod;
y >>= 1;
}
return ans;
}
int main(){
ll n;cin>>n;
ll ans = power(2,n-1,n);
printf("%lld",ans+1);
}