进制转换

4376. 数圈圈

———10->16

十六进制是一种基数为 16 的计数系统，是一种逢 16 进 1 的进位制。
通常用数字 0、1、2、3、4、5、6、7、8、9 和字母 A、B、C、D、E、F 表示，其中: A∼F 表示 10∼15，这些称作十六进制数字。
观察这些数字的图案，我们可以发现，有些数字上面包含圈圈，具体来说：
数字 0,4,6,9,A,D 中包含一个圈。
数字 8,B 中包含两个圈。
数字 1,2,3,5,7,C,E,F 中不含圈。
现在，给定一个十进制整数 n，请你将其转化为十六进制表示，并数一数其十六进制表示中一共含有多少个圈圈。
输入格式
一个整数 n。
输出格式
一个整数，表示整数 n 的十六进制表示包含的圈圈总数。
数据范围
前三个测试点满足 0≤n≤100,
所有测试点满足 0≤n≤2×10^9。
输入样例1：
11
输出样例1：
2
输入样例2：
14
输出样例2：
0

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  6. using namespace std;
  7. int n;
  9. int get(int x,int){
  10.     if(x>=0&&x<=9){
  11.         return x+'0';
  12.     }else{
  13.         return 'A'+x-10;
  14.     }
  15. }
  17. string get(int x){
  18.     string res="";
  19.     if(x==0){  // 必须单独处理一下 0
  20.         return "0";
  21.     }
  22.     while(x){
  23.         res+=get(x%16,0);
  24.         x/=16;
  25.     }
  26.     return res;
  27. }
  29. int cal(string s){
  30.     int res=0;
  31.     for (int i = 0; i < s.size(); i ++ ){
  32.         if(s[i]=='0'||s[i]=='4'||s[i]=='6'||s[i]=='9'||s[i]=='A'||s[i]=='D'){
  33.             res++;
  34.         }else if(s[i]=='8'||s[i]=='B'){
  35.             res+=2;
  36.         }
  37.     }
  38.     return res;
  39. }
  41. int main()
  42. {
  43.     cin >> n;
  44.     string s = get(n);
  45.     cout << cal(s);
  46. }

质数

866. 试除法判定质数

给定 n 个正整数 ai，判定每个数是否是质数。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个正整数 ai。
输出格式
共 n 行，其中第 i 行输出第 i 个正整数 ai 是否为质数，是则输出 Yes，否则输出 No。
输入样例：
2 2 6
输出样例：
Yes No

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  5. using namespace std;
  7. bool is_prime(int n){
  8.     if(n<2){
  9.         return false;
  10.     }
  11.     for (int i = 2; i <= n/i; i ++ ){
  12.         if(n%i==0){
  13.             return false;
  14.         }
  15.     }
  16.     return true;
  17. }
  19. int main(){
  20.     int n;
  21.     cin >> n;
  22.     for (int i = 0; i < n; i ++ ){
  23.         int x;
  24.         cin >> x;
  25.         if(is_prime(x)){
  26.             cout << "Yes"<<endl;
  27.         }else{
  28.             cout << "No" <<endl;
  29.         }
  30.     }
  31. }

867. 分解质因数

给定 nn 个正整数 aiai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。
输入格式
第一行包含整数 nn。
接下来 nn 行，每行包含一个正整数 aiai。
输出格式
对于每个正整数 aiai，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。
每个正整数的质因数全部输出完毕后，输出一个空行。
输入样例：
2 6 8
输出样例：

2 1 3 1

2 3

image.png

  1. #include <iostream>
  2. #include <algorithm>
  4. using namespace std;
  6. void divide(int x)
  7. {
  8.     for (int i = 2; i <= x / i; i ++ )
  9.         if (x % i == 0)
  10.         {
  11.             int s = 0;
  12.             while (x % i == 0) x /= i, s ++ ;
  13.             cout << i << ' ' << s << endl;
  14.         }
  15.     if (x > 1) cout << x << ' ' << 1 << endl;
  16.     cout << endl;
  17. }
  19. int main()
  20. {
  21.     int n;
  22.     cin >> n;
  23.     while (n -- )
  24.     {
  25.         int x;
  26.         cin >> x;
  27.         divide(x);
  28.     }
  30.     return 0;
  31. }

868. 筛质数

给定一个正整数 n，请你求出 1∼n 中质数的个数。
输入格式
共一行，包含整数 n。
输出格式
共一行，包含一个整数，表示 1∼n 中质数的个数。
输入样例：
8
输出样例：
4

  1. #include <iostream>
  2. #include <algorithm>
  4. using namespace std;
  6. const int N= 1000010;
  8. int primes[N], cnt;
  9. bool st[N];
  11. void get_primes(int n)
  12. {
  13.     for (int i = 2; i <= n; i ++ )
  14.     {
  15.         if (!st[i]) primes[cnt ++ ] = i;
  16.         for (int j = 0; primes[j] <= n / i; j ++ )
  17.         {
  18.             st[primes[j] * i] = true;
  19.             if (i % primes[j] == 0) break;
  20.         }
  21.     }
  22. }
  24. int main()
  25. {
  26.     int n;
  27.     cin >> n;
  29.     get_primes(n);
  31.     cout << cnt << endl;
  33.     return 0;
  34. }

约数

869. 试除法求约数

给定 n 个正整数 ai，对于每个整数 ai，请你按照从小到大的顺序输出它的所有约数。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个整数 ai。
输出格式
输出共 n 行，其中第 i 行输出第 i 个整数 ai 的所有约数。
输入样例：
2
6
8
输出样例：
1 2 3 6
1 2 4 8

i 是x的约数，那么n/i也一定是x的约数，所以只要枚举到i<=n/i即可

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <vector>
  6. using namespace std;
  8. vector<int> get_div(int x){
  9.     vector<int>res;
  10.     for (int i = 1; i <= x/i; i ++ ){
  11.         if(x%i==0){
  12.             res.push_back(i);
  13.             if(x/i!=i){
  14.                 res.push_back(x/i);
  15.             }
  16.         }
  17.     }
  18.     sort(res.begin(),res.end());
  19.     return res;
  20. }
  21. int main()
  22. {
  23.     int n;
  24.     cin >> n;
  25.     for (int i = 0; i < n; i ++ ){
  26.         int x;
  27.         cin >> x;
  28.         auto t = get_div(x);
  29.         for(auto c:t){
  30.             cout << c <<" ";
  31.         }
  32.         cout << endl;
  33.     }
  34. }

image.png

870. 约数个数

给定 n 个正整数 ai，请你输出这些数的乘积的约数个数，答案对 109+7 取模。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个整数 ai。
输出格式
输出一个整数，表示所给正整数的乘积的约数个数，答案需对 109+7 取模。
输入样例：
3
2
6
8
输出样例：
12

image.png 依次分解每一个数

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <unordered_map>
  5. #define x first
  6. #define y second
  8. using namespace std;
  9. typedef long long LL;
  10. const int mod = 1e9+7;
  12. unordered_map<int,int>primes;
  14. void get_primes(int x){
  15.     for (int i = 2; i <= x/i; i ++ ){
  16.         while(x%i==0){
  17.             primes[i]++;
  18.             x/=i;
  19.         }
  20.     }
  21.     if(x>1){
  22.         primes[x]++;
  23.     }
  24. }
  26. int main()
  27. {
  28.     int n;
  29.     cin >> n;
  30.     while (n -- ){
  31.         int x;
  32.         cin >> x;
  33.         get_primes(x);
  34.     }
  35.     LL res=1;
  36.     for(auto s:primes){
  37.         res = res * (s.y+1)%mod;
  38.     }
  39.     cout << res;
  40. }

871. 约数之和

给定 n 个正整数 ai，请你输出这些数的乘积的约数之和，答案对 109+7 取模。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个整数 ai。
输出格式
输出一个整数，表示所给正整数的乘积的约数之和，答案需对 109+7 取模。
输入样例：
3
2
6
8
输出样例：
252
image.png

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <unordered_map>
  5. #define x first
  6. #define y second
  8. using namespace std;
  9. typedef long long LL;
  10. const int mod = 1e9+7;
  12. unordered_map<int,int>primes;
  14. void get_primes(int x){
  15.     for (int i = 2; i <= x/i; i ++ ){
  16.         while(x%i==0){
  17.             primes[i]++;
  18.             x/=i;
  19.         }
  20.     }
  21.     if(x>1){
  22.         primes[x]++;
  23.     }
  24. }
  26. int main()
  27. {
  28.     int n;
  29.     cin >> n ;
  30.     for (int i = 0; i < n; i ++ ){
  31.         int x;
  32.         cin >> x;
  33.         get_primes(x);
  34.     }
  35.     LL res=1;
  36.     for(auto s:primes){
  37.         int p = s.x;
  38.         int cnt = s.y;
  39.         LL sum=1;
  40.         for (int i = 1; i <=cnt ; i ++ ){
  41.             sum = (sum * p + 1)%mod;
  42.         }
  43.         res = (res * sum)%mod;
  44.     }
  45.     cout << res;
  46. }

博弈论

891. Nim游戏

给定 n 堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
输入格式
第一行包含整数 n。
第二行包含 n 个数字，其中第 i 个数字表示第 i 堆石子的数量。
输出格式
如果先手方必胜，则输出 Yes。
否则，输出 No。
数据范围
1≤n≤105,
1≤每堆石子数≤109
输入样例：
2
2 3
输出样例：
Yes
image.png

  1. #include <iostream>
  2. #include <cstdio>
  3. using namespace std;
  5. /*
  6. 先手必胜状态：先手操作完，可以走到某一个必败状态
  7. 先手必败状态：先手操作完，走不到任何一个必败状态
  8. 先手必败状态：a1 ^ a2 ^ a3 ^ ... ^an = 0
  9. 先手必胜状态：a1 ^ a2 ^ a3 ^ ... ^an ≠ 0
  10. */
  12. int main(){
  13.     int n;
  14.     scanf("%d", &n);
  15.     int res = 0;
  16.     for(int i = 0; i < n; i++) {
  17.         int x;
  18.         scanf("%d", &x);
  19.         res ^= x;
  20.     }
  21.     if(res == 0) puts("No");
  22.     else puts("Yes");
  23. }

矩阵乘法

1303. 斐波那契前 n 项和

大家都知道 Fibonacci 数列吧，f1=1,f2=1,f3=2,f4=3,…,fn=fn−1+fn−2。
现在问题很简单，输入 n 和 m，求 fn 的前 n 项和 Snmodm。
输入格式
共一行，包含两个整数 n 和 m。
输出格式
输出前 n 项和 Snmodm 的值。
数据范围
1≤n≤2000000000,
1≤m≤1000000010
输入样例：
5 1000
输出样例：
12

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  5. typedef long long LL;
  7. using namespace std;
  8. const int N = 3;
  9. LL n, m;
  11. void mul(LL c[][N], LL a[][N], LL b[][N]) {
  12.     LL temp[N][N] = {0};
  13.     for (int i = 0; i < N; i++) {
  14.         for (int j = 0; j < N; j++) {
  15.             for (int k = 0; k < N; k++) {
  16.                 temp[i][j] = (temp[i][j] + a[i][k] * b[k][j]) % m;
  17.             }
  18.         }
  19.     }
  20.     memcpy(c, temp, sizeof temp);
  21. }
  23. int main() {
  24.     cin >> n >> m;
  25.     if (n <= 2) {
  26.         cout << n % m << endl;
  27.         return 0;
  28.     }
  29.     LL f[N][N] = {{1, 1, 2}};
  30.     n -= 2;
  31.     LL w[N][N] = {
  32.             {0, 1, 1},
  33.             {1, 1, 1},
  34.             {0, 0, 1},
  35.     };
  36.     while (n) {
  37.         if (n & 1) {
  38.             mul(f, f, w);
  39.         };
  40.         n >>= 1;
  41.         mul(w, w, w);
  42.     }
  43.     cout << f[0][2] % m;
  44. }

1304. 佳佳的斐波那契

佳佳对数学，尤其对数列十分感兴趣。
在研究完 Fibonacci 数列后，他创造出许多稀奇古怪的数列。
例如用 S(n) 表示 Fibonacci 前 n 项和 modm 的值，即 S(n)=(F1+F2+…+Fn)modm，其中 F1=F2=1,Fi=Fi−1+Fi−2。
可这对佳佳来说还是小菜一碟。
终于，她找到了一个自己解决不了的问题。
用 T(n)=(F1+2F2+3F3+…+nFn)modm 表示 Fibonacci 数列前 n 项变形后的和 modm 的值。
现在佳佳告诉你了一个 n 和 m，请求出 T(n) 的值。
输入格式
共一行，包含两个整数 n 和 m。
输出格式
共一行，输出 T(n) 的值。
数据范围
1≤n,m≤231−1
输入样例：
5 5
输出样例：
1
样例解释
T(5)=(1+2×1+3×2+4×3+5×5)mod5=1

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  5. typedef long long LL;
  7. using namespace std;
  8. const int N = 4;
  9. LL n, m;
  11. void mul(LL c[][N], LL a[][N], LL b[][N]) {
  12.     LL temp[N][N] = {0};
  13.     for (int i = 0; i < N; i++) {
  14.         for (int j = 0; j < N; j++) {
  15.             for (int k = 0; k < N; k++) {
  16.                 temp[i][j] = (temp[i][j] + a[i][k] * b[k][j]) % m;
  17.             }
  18.         }
  19.     }
  20.     memcpy(c, temp, sizeof temp);
  21. }
  23. int main() {
  24.     cin >> n >> m;
  25.     if (n == 1) {
  26.         cout << 1 % m << endl;
  27.         return 0;
  28.     }else if(n == 2){
  29.         cout << 3 % m <<endl;
  30.         return 0;
  31.     }
  32.     LL f[N][N] = {{1, 1, 2, 1}};
  33.     LL w[N][N] = {
  34.             {0, 1, 1, 0},
  35.             {1, 1, 1, 0},
  36.             {0, 0, 1, 1},
  37.             {0, 0, 0, 1},
  38.     };
  39.     int k = n-2;
  40.     while (k) {
  41.         if (k & 1) {
  42.             mul(f, f, w);
  43.         };
  44.         k >>= 1;
  45.         mul(w, w, w);
  46.     }
  47.     cout << (n*f[0][2]%m+m-f[0][3]%m) % m;
  48. }

1305. GT考试

阿申准备报名参加 GT 考试，准考证号为 n 位数 X1X2⋯Xn，他不希望准考证号上出现不吉利的数字。
他的不吉利数字 A1A2⋯Am 有 m 位，不出现是指 X1X2⋯Xn 中没有恰好一段等于 A1A2⋯Am，A1 和 X1 可以为 0。
输入格式
第一行输入 n,m,K。
接下来一行输入 m 位的不吉利数字。
输出格式
阿申想知道不出现不吉利数字的号码有多少种，输出模 K 取余的结果。
输入样例：
4 3 100
111
输出样例：
81
image.png
image.png
image.png
image.png
image.png

  1. // 常规解法
  2. #include <iostream>
  3. #include <cstring>
  4. #include <algorithm>
  6. using namespace std;
  7. const int M=25,N=1e5;
  8. int ne[M];
  9. string p;
  10. int n,m,K;
  11. int f[N][M];
  13. int main()
  14. {
  15.     cin >> n >> m >> K;
  16.     cin >> p ;
  17.     p = " "+p;
  18.     for (int i = 2,j = 0; i <= m; i ++ ){
  19.         while(j&&p[i]!=p[j+1]){
  20.             j = ne[j];
  21.         }
  22.         if(p[i]==p[j+1]){
  23.             j++;
  24.         }
  25.         ne[i] = j;
  26.     }
  27.     f[0][0] = 1;
  28.     for (int i = 0; i < n; i ++ ){ // 长度
  29.         for (int j = 0; j < m; j ++ ){ // 当前走到模板串哪个位置上
  30.             for (int k = 0; k <= 9; k ++ ){ // 当前的选择
  31.                 int u = j;
  32.                 while(u&&p[u+1]!=k+'0'){
  33.                     u = ne[u];
  34.                 }
  35.                 if(p[u+1]==k+'0'){
  36.                     u = u+1;
  37.                 }
  38.                 //f[i+1][u] = (f[i+1][u] + f[i][j])%K;
  39.                 f[(i+1)&1][u] = (f[(i+1)&1][u] + f[i&1][j])%K;
  40.             }
  41.             f[i&1][j]=0; // 要用滚动数组的话必须这里清零
  42.         }
  43.     }
  44.     int res=0;
  45.     for (int j = 0; j < m ; j ++ ){
  46.         res = (res + f[n&1][j])%K;
  47.     }
  48.     cout << res;
  49. }
  1. // 矩阵乘法
  2. #include <iostream>
  3. #include <cstring>
  4. #include <algorithm>
  6. using namespace std;
  7. int n,m,K;
  8. const int N = 25;
  9. int ne[N];
  10. int A[N][N];
  11. int f[N][N];
  12. string p;
  14. void mul(int c[][N],int a[][N],int b[][N]){
  15.     int t[N][N];
  16.     memset(t, 0, sizeof t);
  17.     for (int i = 0; i < m; i ++ ){
  18.         for (int j = 0; j < m; j ++ ){
  19.             for (int k = 0; k < m; k ++ ){
  20.                 t[i][j] = (t[i][j] + a[i][k]*b[k][j])%K;  
  21.             }
  22.         }
  23.     }
  24.     memcpy(c,t,sizeof t);
  25. }
  27. void qmi(){
  28.     f[0][0]=1;
  29.     while(n){
  30.         if(n&1){
  31.             mul(f,f,A);
  32.         }
  33.         n>>=1;
  34.         mul(A,A,A);
  35.     }
  36.     int res=0;
  37.     for (int i = 0; i < m; i ++ ){
  38.         res = (res + f[0][i])%K;
  39.     }
  40.     cout << res;
  41. }
  43. int main()
  44. {
  45.     cin >> n >> m >> K; // m是p串的长度
  46.     cin >> p;
  47.     p = " "+p;
  48.     // 求ne数组
  49.     for (int i = 2,j=0; i <= m; i ++ ){
  50.         while(j&&p[i]!=p[j+1]){
  51.             j = ne[j];
  52.         }
  53.         if(p[i]==p[j+1]){
  54.             j++;
  55.         }
  56.         ne[i]=j;
  57.     }
  58.     // 求A矩阵
  59.     for (int i = 0; i < m; i ++ ){
  60.         for (int j = 0; j <= 9; j ++ ){
  61.             int u = i;
  62.             while(u&&p[u+1]!=j+'0'){
  63.                 u = ne[u];
  64.             }
  65.             if(p[u+1]==j+'0'){
  66.                 u++;
  67.             }
  68.             if(u<m){
  69.                 A[i][u]++;
  70.             }
  71.         }
  72.     }
  73.     //快速幂
  74.     qmi();
  76. }