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;
}