欧拉函数
在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目，记作φ(n). φ(1)=1
1、分解质因子，求出质因子p
2、将p带入，套公式
为了代码方便，套第三个公式
#include <iostream> using namespace std; int phi(int x) { int res = x; for (int i = 2; i <= x / i; i ++ ) if (x % i == 0) { //欧拉计算公式，等价于res*=(1-1/p),防止小数导致精度丢失 res = res / i * (i - 1); while (x % i == 0) x /= i; } if (x > 1) res = res / x * (x - 1); return res; } int main() { int n; cin >> n; while (n -- ) { int x; cin >> x; cout << phi(x) << endl; } return 0; }
补充：
若a与m互质 ，则有
快速幂
大佬算法讲解：
举个栗子：
如上例所示：
利用a取平方操作，构建k的2的次幂和
#include <iostream> using namespace std; typedef long long LL; int quick_pow(int a, int k, int p)//二进制优化 { int res = 1 % p;//表示取模总值 while (k) { if (k & 1) res = (LL)res * a % p;//相乘等价于a的次幂相加,使得k=2的次幂和 k >>= 1; a = (LL)a * a % p;//使k进制进一位 } return res; } int n; int main() { cin >> n; while (n--) { int a, k, p; cin >> a >> k >> p; cout << quick_pow(a, k, p) << endl; } return 0; }
求组合数 I
如上公式：从a个苹果里选b个的选法=包含红苹果的选法+不包含红苹果的选法；
包含：除去必选的红苹果，就是在a-1个苹果里选b-1个的选法
不包含：直接丢掉红苹果，在a-1个苹果里选b个
#include <iostream> #include <algorithm> using namespace std; const int N = 2010, mod = 1e9 + 7; int c[N][N]; void init()//预处理 { for (int i = 0; i < N; i ++ ) for (int j = 0; j <= i; j ++ ) if (!j) c[i][j] = 1;//i==0时j必等于0,初始化c[0][0] else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;//套公式 } int main() { int n; init(); scanf("%d", &n); while (n -- ) { int a, b; scanf("%d%d", &a, &b); printf("%d\n", c[a][b]); } return 0; }
博弈论
Nim游戏
结论：
先手必败状态：a1 ^ a2 ^ a3 ^ ... ^an = 0
先手必胜状态：a1 ^ a2 ^ a3 ^ ... ^an ≠ 0
1、若处于 先手必败状态，则无论怎么操作，之后都会变成先手必胜状态
2、若处于 先手必胜状态，则必有一次操作能使得状态变为先手必败状态
记忆：
当所有值相同，如剩下2 2两堆，先手无论怎么操作，后手只需要做镜像操作即可胜利；记忆特殊情况，当所有值相同，则a1 ^ a2 ^ a3 ^ ... ^an = 0，则先手必败
#include <iostream> #include <cstdio> using namespace std; /* 先手必胜状态：先手操作完，可以走到某一个必败状态 先手必败状态：先手操作完，走不到任何一个必败状态 先手必败状态：a1 ^ a2 ^ a3 ^ ... ^an = 0 先手必胜状态：a1 ^ a2 ^ a3 ^ ... ^an ≠ 0 */ int main(){ int n; scanf("%d", &n); int res = 0; for(int i = 0; i < n; i++) { int x; scanf("%d", &x); res ^= x; } if(res == 0) puts("No"); else puts("Yes"); }
