UVA10006 Carmichael Numbers

题目链接：UVA10006 Carmichael Numbers

题意：若 $\forall x (1<x<n) ,x^n\equiv x \mod n$ ，且 $n$ 为合数，则称 $n$ 为Carmichael Numbers，多组数据判断 $n$ 是否是这种数

数据范围 $2<n<65000$

合数好处理，直接 $O(\sqrt{n})$ 暴力判断即可

那么 $x^n$ 怎么处理呢？

如果我们去一个一个乘，时间复杂度 $O(n^2)$ ，直接TLE

因此，我们要用到快速幂

对于 $x^k$ ，根据整数的唯一分解定理和常识，$k$ 可以写成唯一的二进制形式

则 $x^k$ 可以被分解为它二进制位上每一个 $1$ 的幂的乘积

例如： $x^{(5)_{10}} = x^{(101)_2} = x^{(100)_2} \times x^{(1)_2} = x^{(4)_{10}} \times x^{(1)_{10}}$

那么我们只需要把 $k$ 不断右移一位，看它最后一位是否为 $1$ ，是就乘上对应的数即可

因此我们就可以在 $O(n\log{n})$的时间搞定这题了

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define R register
int n;
bool prime(R int x)
{
	if(x<2)return 0;
	for(R int i=2; i*i<=x; i++)
		if(!(x%i))return 0;
	return 1;
}
int qpow(R int a,R int b)
{
	R int ans=1,base=a%n;
	while(b)
	{
		if(b&1)ans=ans*base%n;
		base=base*base%n; // 要取模，不然中间就溢出了
		b>>=1;
	}
	return ans;
}
void proc()
{
	if(prime(n))
	{
		printf("%lld is normal.\n",n);
		return;
	}
	for(R int x=2; x<n; x++)
		if(qpow(x,n)%n!=x)
		{
			printf("%lld is normal.\n",n);
			return;
		}
	printf("The number %lld is a Carmichael number.\n",n);
}
signed main()
{
	while(~scanf("%lld",&n)&&n)
		proc();
	return 0;
}