AC题解

#include<bits/stdc++.h>
using namespace std;
long long s(long long n,long long m)
{
	if(!m)return 1;
	if(m==1)return 2;
	long long ans;
	ans=s(n,m/2)%n;
	ans=ans*ans%n;
	if(m%2==1)ans=ans*2%n;
	return ans;
}
int main()
{
	long long n,ans;
	while(scanf("%I64d",&n)&&n)
	{
		ans=(s(n,n-1)+1)%n;
		printf("%lld\n",ans);
	}
	return 0;
}