1、费解的开关https://ac.nowcoder.com/acm/contest/998/D
题目大意：如图。
分析：简单分析可知，每个开关至多点击1次，因为你同一个开关点2次又反转回来了相当于没点，而且题目求最小次数，因此可以得出性质1：每个开关至多点击一次。
当某一行的开关状态被锁死了、不允许点击该行的开关了，那么下面的所有状态也就确定了！这个可以递推得到。想法就是，当这一行的开关已经锁死，不允许点击了，当这一行还存在0，那么这个0下方的开关必须要点击一次！
因此，可以得知，只要确定第一行的状态，后面的情况也就确定了，而第一行的状态只有2^5 种也就是[0--2^5] 种点击状态，即一次都不点击（也可能是最优）和五个都点击一次（也可能是最优）。
实现思路：暴力枚举第一行的所有情况，可以用二进制来表示当前状态。接着就是模拟后面的每一行的变化，每一种情况都去更新一个min ans
ac代码：
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int inf = 0x3f3f3f3f;
bool g[6][6];
void change(string a[], int x, int y){//改变该坐标周围四个点+本身该点的操作函数
a[x][y] == '1' ? a[x][y] = '0' : a[x][y] = '1';
int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};
for(int i = 0; i < 4; i ++){
if(x + dx[i] >= 0 && x + dx[i] <= 4 && y + dy[i] >= 0 && y + dy[i] <= 4){
a[x + dx[i]][y + dy[i]] == '1' ? a[x + dx[i]][y + dy[i]] = '0' : a[x + dx[i]][y + dy[i]] = '1';
}
}
}
int gettime(string a[]){
string b[5];for(int i = 0; i < 5; i ++) b[i] = a[i];//备份一份图
int time = 0;//需要操作的次数
for(int i = 0; i < 5; i ++)
if(g[0][i]) {change(b, 0, i); time++;}//每一种变化的状态
for(int i = 1; i < 5; i ++){//模拟后面4行的变化状态，看'0'
for(int j = 0; j < 5; j ++){
if(b[i - 1][j] == '0') {
change(b, i, j);
time ++;
if(time > 6) return inf;
}
}
}
for(int i = 0; i < 5; i ++)//最后必须检查最后一行是否有0
if(b[4][i] == '0') return inf;
return time;
}
void so(){
string a[5];
for(int i = 0; i < 5; i ++) cin >> a[i];
int ans = inf;
for(int i = 0; i < 1 << 5; i ++){//二进制枚举所有情况
int temp = 0;
memset(g, 0, sizeof g);
for(int j = 0; j < 5; j ++)//判断每一位上是否为1
if((i >> j) & 1)
g[0][j] = 1;
temp = gettime(a);
ans = min(ans, temp);
}
if(ans == inf) cout << -1 << endl;
else cout << ans << endl;
}
int main(){
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int t;
cin >> t;
while(t--) so();
return 0;
}
2、sumdivhttps://ac.nowcoder.com/acm/contest/998/F
题目大意：给你A B两个数，求A^B 这个值所有的约束之和。
分析：数论。用到的数学知识：任何一个正整数可以唯一地被质因子的次幂 之积表示，如右图：
这里得强调一个概念：一个数的质因子是指p1、p2、........pk之间是互质的。
比如pi分别等于1 2 3 5 7.....，这些p之间是互质的关系。用这些p的α次方之积可表示正整数。
这是知识点。对应的代码：
/*分解质因数：试除法
最慢O(sqrt(n)) 最快logn
*/
#include <bits/stdc++.h>
using namespace std;
void divide(int x){//x是要分解的那个数
for(int i = 2; i <= x / i; i ++){//这里也可以写成for(int i = 2; i * i <= x; i ++)
if(x % i == 0){//如果i是x的一个因子
int α = 0;
while(x % i == 0){//不断地除以这个因子，得到该因子的次幂α
x = x / i;
α ++;
}
cout << i << " " << α << '\n';//输出pi^αi
}
}
if(x > 1) cout << x << ' ' << 1 << '\n';//如果最终x没有被完全分解，说明它本身就是质数，x = x^1
}
(对应上方代码第18行)
还有另一个知识点。约数之和。
以上的公式怎么理解？
约束的个数为什么是相乘的关系？因为每个分解出来的因子之间是互质的！因此他们的次幂αi也就代表了他们有几个pi连乘，因为pi和pj之间是互质的，那么pi的次幂之间也是互质的。
例如假设某个数x被分解成：pi = 2, pj = 3，两者的次幂 再相乘
假设pi的αi = 4， pj的αj = 3；
相乘的关系，得到的值都不一样，但是都是x的因子。
感受到数学的奥妙了！
另一个知识点约数之和怎么理解？它为什么是各部分的和，再相乘？
首先是各部分的和，这个比较好理解，该部分都是pi的次幂的和，这些pi的次幂都是x的约数，因此拿他们来和也是合理的。但是各部分之间是相乘的关系怎么理解？
还是举简单的2个的例子：
代码实现思路：
先分解质因数。分解到该质因数的同时，ans = ans 乘上 sum(该质因子那部分的和)。
但是此处求sum需要用到分治的思想，对公式又进行了降解！
这个分治也比较难想到。积累积累思路。
ac代码：
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int mod = 9901;
int qmi(int a, int b){
int res = 1;
a %= mod;
while(b){
if(b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
int sum(int p, int k){
if(k==1) return 1;
if(k % 2 == 0) return (1 + qmi(p, k / 2)) * sum(p, k / 2) % mod;
else return (qmi(p, k - 1) + sum(p, k - 1)) % mod;
}
int main(){
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int a, b;
cin >> a >> b;
int res = 1;
//分解质因子
for(int i = 2; i * i <= a; i ++){
if(a % i == 0){//i正好是一个因子
int s = 0;
while(a % i == 0){//将该因子一直剥离开，例如一直除,拿到该质因子的次幂数α
a = a / i;
s ++;
}
res = res * sum(i, b * s + 1) % mod;
}
}
if(a > 1) res = res * sum(a, b + 1) % mod;
if(a == 0) res = 0;
cout << res << endl;
return 0;
}