4的幂(同余问题)
作者:
hayate
,
2024-02-13 11:07:29
,
所有人可见
,
阅读 60
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n;
// 定义一个函数用于判断整数n是否为4的幂次方
bool isPowerofFour(int n)
{
// 判断一个数是否为4的幂次方需要满足两个条件:
// 1. 它必须是2的幂次方,即它的二进制表示中有且只有一个1(n & (n - 1)) == 0 确保这一点)
// 2. 在2的幂次方的基础上,这个唯一的1必须出现在从低位开始的偶数位置上(即1、4、16、64...)
// 这可以通过n % 3 == 1来判断。因为4的幂次方减1总是3的倍数(4^k - 1 = (2^2)^k - 1 = (2^k - 1)(2^k + 1),
// 其中(2^k - 1)和(2^k + 1)分别是两个连续的奇数,所以它们的乘积是3的倍数)
// 同时,n必须大于0,因为0不是4的幂次方
return (n > 0) && ((n & (n - 1)) == 0 && n % 3 == 1);
}
int main()
{
cin >> n; // 输入一个整数n
cout << isPowerofFour(n) << endl; // 调用函数判断n是否为4的幂次方,并输出结果
return 0;
}