蓝桥杯题型分布2

蓝桥杯题型分类2

素数

孪生素数

传送门

#include <bits/stdc++.h>
using namespace std;// 定义最大范围，m <= 100，因此数组大小只需要开到 110 即可
const int N = 1e2 + 10;// primes 用于存储素数，cnt 记录素数的数量
int primes[N], cnt;
// st[i] 如果为 true 表示 i 已经被筛选掉（非素数）
bool st[N];// 获取 [2, n] 范围内的所有素数，采用线性筛法
void get_primes(int n) {for (int i = 2; i <= n; i++) {// 如果 st[i] 为 false，说明 i 还是素数if (!st[i]) {// 将该素数存入 primes 数组，并计数primes[cnt++] = i;}// 遍历用来进行筛选的素数列表for (int j = 0; primes[j] <= n / i; j++) {// 将当前下标对应的合数标记为 truest[primes[j] * i] = true;// 若当前数 i 能被 primes[j] 整除，就退出，避免重复筛if (i % primes[j] == 0) break;}}
}int main() {int m;cin >> m;  // 读取输入// 获取 [2, m] 范围内所有素数get_primes(m);// 从后往前遍历 primes 数组，查找相隔为 2 的孪生素数对for (int i = cnt - 1; i >= 1; i--) {// 检查相邻两素数之差是否为 2if (primes[i] - primes[i - 1] == 2) {// 输出这对最大孪生素数cout << primes[i - 1] << " " << primes[i];break;}}return 0;
}

素数个数

传送门

朴素筛法求素数

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉void get_primes(int n)
{for (int i = 2; i <= n; i ++ ){if (st[i]) continue;primes[cnt ++ ] = i;for (int j = i + i; j <= n; j += i)st[j] = true;}
}

线性筛法求素数

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉void get_primes(int n)
{for (int i = 2; i <= n; i ++ ){if (!st[i]) primes[cnt ++ ] = i;for (int j = 0; primes[j] <= n / i; j ++ ){st[primes[j] * i] = true;if (i % primes[j] == 0) break;}}
}

因数分解

传送门

试除法分解质因数

void divide(int x)
{for (int i = 2; i <= x / i; i ++ )if (x % i == 0){int s = 0;while (x % i == 0) x /= i, s ++ ;cout << i << ' ' << s << endl;}if (x > 1) cout << x << ' ' << 1 << endl;cout << endl;
}

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll N=1e12;void divide(ll x)
{for(ll i=2;i<=x/i;i++){if(x%i==0){int s=0;while(x%i==0){x/=i;s++;}if(s==1){cout<<i<<" * ";}else{cout<<i<<'^'<<s<<" * ";}}}if(x>1)cout<<x<<endl;
}
void solve()
{ll n;cin>>n;divide(n);
}
int main()
{solve();return 0;
}

等差素数列

传送门

#include <bits/stdc++.h>
using namespace std;// 使用ll表示long long，方便处理较大数值
using ll = long long;// N 定义为 1e8，表示可能存储的最大范围
const ll N = 1e8;// primes 数组用于存储素数，cnt 表示当前素数数量
int primes[N], cnt;
// st 数组标记某个数是否为合数，如果 st[x] = true，表示 x 不是素数
bool st[N];// 筛选素数函数，埃氏筛或线性筛的思路
void get_primes(int n)
{// 从 2 开始判断每个数for(int i = 2; i <= n; i++){// 如果 st[i] == false，说明 i 是素数if(!st[i]) primes[cnt++] = i;// 使用已得到的素数来标记合数for(int j = 0; primes[j] <= n / i; j++){// 将 i * primes[j] 标记为合数st[primes[j] * i] = true;// 如果 i 能被当前素数整除，则无需再继续标记if(i % primes[j] == 0) break;}}
}int main()
{// 先筛选出 10000 以内的素数get_primes(10000);// 枚举可能的首项，从 2 开始到 10000for(int head = 2; head <= 10000; head++){// 如果 head 是素数（st[head] == false），再去尝试不同的公差 dif(!st[head]){// 从公差 d=2 开始枚举到 1000for(int d = 2; d <= 1000; d++){// len 用于统计当前等差序列中连续的素数个数，这里初始设为 1int len = 1;// 从 head 开始，每次加上公差 dfor(int j = head; ; j += d){// 如果当前数 j 仍为素数if(!st[j]){len++;// 当连续素数个数达到 10 时，说明找到一个长度为 10 的等差素数序列if(len == 10){// 输出此时的公差 d 并直接结束cout << d << endl;return 0;}}// 遇到合数时，当前公差无法构成长度 10 的素数序列，跳出循环else{break;}}}}}return 0;
}

梅森素数

梅森素数

在这段程序中，a[1] 初始化为 1，然后在整个运算过程中它并不会回到 0。
具体原因是：
• a[1] 一开始被设为 1（代表当前值的最低位）。
• 随后的循环每次都对所有位进行乘 2 运算，此时最低位始终会在 2、4、8、6 之间循环（或产生进位后继续保持非零），不会变为 0。
• 最后减去 1 时，也只是在原先非零的最低位上进行简单的 -1 操作，因此不会出现 a[1] 是 0 而再继续减 1 的问题。

#include <iostream>
#include <vector>
using namespace std;int main()
{// 初始化一个大小为101的整型向量a，所有元素初始为0，用于模拟“高精度”存储数字的每一位。// 下标1到100将存储数字的各位（下标1表示最低位，100最高位）。vector<int> a(101, 0);// 将最低位初始化为1，相当于保存数字"1"。a[1] = 1;// 这层循环共执行11213次，相当于做 2^11213 的计算for (int i = 1; i <= 11213; ++i) {int c = 0; // c用来记录进位// 将每一位都乘以2，再加上上一位留下的进位cfor (int j = 1; j <= 100; ++j) {a[j] = a[j] * 2 + c;   // 乘2并加进位c = a[j] / 10;        // 计算新的进位值a[j] %= 10;           // 当前位保留一位，超过10的部分变成下一位进位}// 此时若c不为0，说明还产生新的进位，不过只要求后100位，不再额外处理进位}// 计算 2^11213 - 1，即将结果最低位减1a[1] -= 1;// 从最高位到最低位输出，拼接成完整的数字串for (int i = 100; i >= 1; --i) {cout << a[i];}return 0;
}

组素数

组素数

#include <bits/stdc++.h>
using namespace std;
using ll=long long;const int N=1e4;
int primes[N],cnt;
bool st[N];void get_primes(int n)
{for(int i=2;i<=n;i++){if(!st[i])primes[cnt++]=i;for(int j=0;primes[j]<=n/i;j++){st[primes[j]*i]=true;if(i%primes[j]==0)break;}}
}
int main()
{get_primes(10000);int ans=0;if (!st[1949]) ans++;if (!st[1499]) ans++;if (!st[1994]) ans++;if (!st[4199]) ans++;if (!st[4919]) ans++;if (!st[4991]) ans++;if (!st[9914]) ans++;if (!st[9941]) ans++;if (!st[9419]) ans++;if (!st[9491]) ans++;cout<<ans;return 0;
}

素数环

素数环

#include <bits/stdc++.h>
using namespace std;
const int N = 1000000;/*全局变量说明:- n: 输入的整数 n (1 ~ n 的所有数字需要组成素数环).- ans: 用于存储当前构造的排列环.- used[i]: 标记数字 i 是否已经被放入环中(default false).- ok: 用于在最后判断是否输出过解, 若一直为 false 表示无解.
*/// 数组范围较大以防越界, 但实际 n < 20 即可
int n;
vector<int> ans;
bool used[N];
bool ok; // 是否已经找到或输出过解// 判断 x 是否为素数的函数
bool check(int x) {if (x < 2) return false;for (int i = 2; i * i <= x; i++) {if (x % i == 0) {return false;}}return true;
}/*dfs(u) 表示已经在 ans 中放入了 u 个数字 (其中 ans[0] = 1 已固定),接下来要尝试放第 (u+1) 个数字. 
*/
void dfs(int u) {// 如果已经放满 n 个数字, 检查首尾之和是否是素数if (u >= n) {int firstnum = ans[0];int lastnum = ans[n-1];int sum = firstnum + lastnum;// 如果首尾之和为素数, 则输出该排列if (check(sum)) {ok = true;for (auto x : ans) {cout << x << " ";}cout << endl; }return; }// 尝试在位置 u 放所有可用数字 i (1 <= i <= n)for (int i = 1; i <= n; i++) {if (!used[i]) {// 取当前环的最后一个数字与 i 相加, 若为素数才可放置int sum = ans.back() + i;if (check(sum)) {ans.push_back(i);used[i] = true;// 继续放下一个位置dfs(u + 1);// 回溯, 恢复状态ans.pop_back();used[i] = false;    }}}
}int main() {cin >> n;// 先将数字 1 放入环 (作为第一个元素), 并标记已用used[1] = true;ans.push_back(1);// 从第 2 个位置开始尝试放数字, 因为第一个位置已固定 1dfs(1);// 如果一直没有输出答案, 输出 "No Answer"if (!ok) {cout << "No Answer";}return 0;
}

找素数(分段筛）

找素数

#include <bits/stdc++.h>
using namespace std;/*题意: 给定区间 [a, b] (2 ≤ a ≤ b ≤ 2147483647 且 b - a ≤ 1000000)，求其中的素数个数。算法: "分段筛" (Segmented Sieve)- 步骤:1) 先用传统埃氏筛法在 [2, sqrt(b)] 区间内找出所有素数，并存放到 primes 容器中。2) 在要处理的区间 [a, b] 内，创建一个布尔数组 isPrimeSegment，默认都设为 true。3) 用前面找到的小素数集合 primes 来标记 [a, b] 区间中的合数。若 p 为小素数，则从 max(p * p, ceil(a/p)*p) 开始，每隔 p 步将对应位置标记为 false。4) 统计未被标记的数即为该区间内的素数个数。若 a <= 1，则特判排除 0、1。复杂度:- 第1步在 sqrt(b) 内作普通筛，复杂度约 O( sqrt(b) log log sqrt(b) )。- 第2、3步对区间长 (b - a + 1) 作标记，最多 1,000,001 长度，可行。注意事项:- 需要用 64 位类型 (long long 或 int64_t) 存储 b 的开根与下标计算。- 避免越界。
*/static const int MAXN = 1000000; // b-a <= 1000000
// 用来存 [2, sqrt(b)] 中所有素数
vector<long long> primes;// 普通埃氏筛, 获得 [2..upper] 以内所有素数
void getPrimesUpTo(long long upper) {// 使用简单的布尔数组进行标准筛法vector<bool> isPrime(upper + 1, true);isPrime[0] = false;isPrime[1] = false;for(long long i = 2; i * i <= upper; i++) {if(isPrime[i]) {for(long long j = i * i; j <= upper; j += i) {isPrime[j] = false;}}}// 将筛出的素数放到 primes 容器中for(long long i = 2; i <= upper; i++) {if(isPrime[i]) {primes.push_back(i);}}
}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);long long a, b;cin >> a >> b; // 特判：若区间起点小于 2，将其拉到 2if(a < 2) a = 2;// 第 1 步: 筛出 [2, sqrt(b)] 的所有素数long long limit = (long long)floorl(sqrtl((long double)b));getPrimesUpTo(limit);// 第 2 步: 根據区间 [a, b] 建立 isPrimeSegment 数组long long segmentSize = b - a + 1; vector<bool> isPrimeSegment(segmentSize, true); // 默认都当作素数// 第 3 步: 用上一步 primes 标记区间 [a, b] 内的合数for(long long p : primes) {if((long long)p * p > b) break; // 超出区间上界则停止// 找到 [a, b] 区间内, 以 p 为步长需要开始标记的位置long long start = max((long long)p * p, ( (a + p - 1) / p ) * p);for(long long x = start; x <= b; x += p) {isPrimeSegment[x - a] = false;}}// 第 4 步: 统计 isPrimeSegment 中为 true 的个数long long countPrime = 0;for(long long i = 0; i < segmentSize; i++) {if(isPrimeSegment[i]) countPrime++;}cout << countPrime << "\n";return 0;
}

连续素数和

连续素数和

#include <bits/stdc++.h>
using namespace std;const int N = 1e4 + 10;
using ll = long long;int primes[N], cnt;  // primes[] 用于存储已筛出的素数，cnt 表示素数总数量
bool st[N];          // st[x] 表示 x 是否是合数；true 表示合数，false 表示尚未判断为合数// 筛出 [2..n] 范围内的所有素数，保存到 primes[]，并更新 cnt
void get_primes(int n) {for (int i = 2; i <= n; i++) {if (!st[i]) {primes[cnt++] = i;}for (int j = 0; j < cnt && (long long)primes[j] * i <= n; j++) {st[primes[j] * i] = true;if (i % primes[j] == 0) {break;}}}
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);// 先筛出 2..N 范围内的素数get_primes(N);while (true) {int n;cin >> n;if (!cin || n == 0) {break;}int ans = 0;// 遍历所有连续子区间 [i..j]for (int i = 0; i < cnt; i++) {ll sum = 0;// 连续累加for (int j = i; j < cnt; j++) {sum += primes[j];if (sum > n) {// 过大则不必继续累加break;}if (sum == n) {ans++;}}}cout << ans << "\n";}return 0;
}

小明的素数对

小明的素数对

#include <bits/stdc++.h>
using namespace std;const int N = 100000 + 10;  
int primes[N], cnt;         // primes数组存储素数，cnt记录素数个数
bool st[N];                 // st数组标记是否为素数，st[i] = true 表示 i 不是素数void get_primes(int n) {for (int i = 2; i <= n; i++) {if (!st[i]) primes[cnt++] = i;  for (int j = 0; j < cnt && primes[j] <= n / i; j++) {st[primes[j] * i] = true; if (i % primes[j] == 0) break;  }}
}int main() {int n;cin >> n;               get_primes(n);         int ans = 0;            // 遍历 primes 数组，枚举所有的素数对 (p1, p2)for (int i = 0; i < cnt; i++) {for (int j = i + 1; j < cnt; j++) {int diff = primes[j] - primes[i];  // 计算素数对的差// 检查差 diff 是否在范围内，且为素数if (2 <= diff && diff <= n && !st[diff]) {ans++;  }}}cout << ans << endl;    return 0;
}

疑似素数

传送门

#include <bits/stdc++.h>
using namespace std;const int N = 1e6+10;  
int primes[N], cnt;         // primes数组存储素数，cnt记录素数个数
bool st[N];                 // st数组标记是否为素数，st[i] = true 表示 i 不是素数void get_primes(int n) {st[1]=true;st[0]=true;for (int i = 2; i <= n; i++) {if (!st[i]) primes[cnt++] = i;  for (int j = 0; j < cnt && primes[j] <= n / i; j++) {st[primes[j] * i] = true; if (i % primes[j] == 0) break;  }}
}int solve(int x)
{int sum=0;string s=to_string(x);for(int i=0;i<s.size();i++){sum+=s[i]-'0';}return sum;
}
int main() 
{int n;cin>>n;int ans=0;get_primes(N);for(int i=2;i<=n;i++){int sum=solve(i);if(!st[sum]){ans++;}}cout<<ans;return 0;
}

质数拆分

质数拆分

这里，若干两两不同的质数之和，这里其实很容易想到首先我们要求出2019内的所有质数，这个打个表就好了，其次两两不同，我们应该要想到动态规划。

这里设dp[i][j]表示前i个质数，可以两两不同加起来等于j的方案数。

如果当前j>=prime[i]，说明当前的质数可以取，取完后我们只要看j-prime[i]有多少种取法，那么方案数之中有部分为dp[i-1][j-prime[i]]种，另外一部分是不取当前的质数prime[i]，即dp[i-1][j]。若j<prime[i]，说明当前我们取不了prime[i]，只有上面两种情况下的后一种即dp[i-1][j]。

其次，我们怎么初始化呢？我们初始化dp[0][0]=1，这样我们就能在第一次质数2的时候初始化了。

#include <iostream>
using namespace std;const int N=10000;
const int M=2020;
long long dp[M][M];int primes[N], cnt;
bool st[N];         void get_primes(int n)
{for (int i = 2; i <= n; i++){if (!st[i]) {primes[cnt++] = i;}for (int j = 0; j < cnt; j++){// 如果当前primes[j]*i超过n，则可跳出循环long long t = (long long)primes[j] * i;if (t > n) break;st[t] = true;if (i % primes[j] == 0) break;}}
}int main()
{get_primes(2019);dp[0][0] = 1;// i从1开始到cnt，但使用primes[i-1]for(int i = 1; i <= cnt; i++){int p = primes[i-1];for(int j = 0; j <= 2019; j++){dp[i][j] = dp[i-1][j];if(j >= p) {dp[i][j] += dp[i-1][j - p];}}}cout << dp[cnt][2019] << endl;return 0;
}

将dp改为一维数组

#include <iostream>
using namespace std;static const int M = 2020; // 要覆盖到 2019
long long dp[M];int primes[10000], cnt;
bool st[10000];void get_primes(int n)
{for(int i = 2; i <= n; i++){if(!st[i]) primes[cnt++] = i;for(int j = 0; j < cnt; j++){long long t = (long long)primes[j] * i;if(t > n) break;st[t] = true;if(i % primes[j] == 0) break;}}
}int main()
{get_primes(2019);dp[0] = 1;// 使用 下标 i ∈ [0, cnt-1]，对应第 i 个质数for(int i = 0; i < cnt; i++){int p = primes[i];for(int j = 2019; j >= p; j--){dp[j] += dp[j - p];}}cout << dp[2019] << endl;return 0;
}

纯质数

纯质数

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=20210605+10;
int primes[N],cnt;
bool st[N];// 标记是否为合数，st[i]=false => i是质数或i=1void get_primes(int n)
{for(int i=2;i<=n;i++){if(!st[i])primes[cnt++]=i;for(int j=0;primes[j]<=n/i;j++){st[primes[j]*i]=true;if(i%primes[j]==0)break;}}
}bool solve(int x)// 判断整数 x 的每个十进制位是否都是 2,3,5,7
{while(x>0){int d = x%10;if(d!=2 && d!=3 && d!=5 && d!=7) {return false;}x/=10;}return true;
}int main()
{int ans=0;get_primes(20210605);for(int i=2;i<=20210605;i++){if(!st[i])// i是质数{if(solve(i)){ans++;}}}cout<<ans;return 0;
}

超级质数

超级质数

#include <bits/stdc++.h>
using namespace std;
/*
1.10以内的质数有2，3，5，7
2.根据超级质数的组成规则可以组成23，37，53，57，73这样的相邻质数组合,
满足要求的有23，37，53，73 
3.根据这些组合可以组成237，373，573，737这样的数字组合，满足要求的只有373
4.根据组成规则已经不能在373的基础之上进行组合，即为最大超级质数 
*/
bool is_primes(int x)
{if(x<2)return false;for(int i=2;i<=x/i;i++){if(x%i==0){return false;}}return true;}
int main()
{// int n;// while(1)// {//   cin>>n;//   if(is_primes(n))//   {//     cout<<"是素数"<<endl;//   }//   else //   {//     cout<<"不是素数"<<endl;//   }// }cout<<373;return 0;
}

质数日期

质数日期

暴力做法

#include <bits/stdc++.h>
using namespace std;const int N=3e7+10;
using ll=long long;int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉
void get_primes(int n)
{for (int i = 2; i <= n; i ++ ){if (!st[i]) primes[cnt ++ ] = i;for (int j = 0; primes[j] <= n / i; j ++ ){st[primes[j] * i] = true;if (i % primes[j] == 0) break;}}
}int months[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
bool check(int date)
{int year=date/10000,month=date%10000/100,day=date%100;if(!month||month>=13||!day)return false;if(month!=2&&day>months[month])return false;if(month==2){int leap=(year%4==0&&year%100!=0)||year%400==0;if(day>28+leap)return false;}return true;
}
int main()
{ll s,t;cin>>s>>t;get_primes(t);int cnt=0;for(int i=s;i<=t;i++){if(check(i)){if(!st[i]){cnt++;}}}cout<<cnt;return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;typedef long long LL;const int N = 100010;int n;
int f[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
int primes[N],cnt;
bool st[N];void get_primes(int n)
{for(int i = 2;i <= n;i++){if(!st[i]) primes[cnt++] = i;for(int j = 0;primes[j] <= n / i;j++){st[primes[j] * i] = true;if(i % primes[j] == 0) break;}}
}bool check(int n)
{if((n % 400 == 0) || (n % 4 == 0 && n % 100 != 0)) return true;return false;
}int main()
{get_primes(N - 1);LL a,b;cin >> a >> b;int res = 0;for(int i = a / 10000;i <= b / 10000;i++){if(check(i)) f[2] = 29;else f[2] = 28;for(int j = 1;j <= 12;j++){for(int k = 1;k <= f[j];k++){LL p = i * 10000ll + j * 100ll + k;if(p < a) continue;else if(p > b) break;else{bool flag = true;for(int l = 0;l < cnt && (LL)primes[l] * primes[l] <= p;l++)if(p % primes[l] == 0){flag = false;break;}if(flag){res++;}}}}}cout << res << '\n';return 0;
}

质数游戏2

质数游戏2

#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 10; // 定义素数的最大值int primes[N], cnt;     // primes[] 存储素数，cnt计数素数的数量
bool st[N];            // st[x] 存储 x 是否被筛掉// 函数用于获取1到 n 的所有素数
void get_primes(int n) {for (int i = 2; i <= n; i++) {if (!st[i]) primes[cnt++] = i; for (int j = 0; primes[j] <= n / i; j++) { st[primes[j] * i] = true; if (i % primes[j] == 0) break; }}
}int ans; // 计数满足条件的子序列数量
int n; // 序列长度
int a[N]; // 存放数字序列// DFS函数
void dfs(int u, int cnt, int sum) { // u: 当前遍历位置，cnt:当前子序列数字个数，sum:当前子序列数字和// 当 u 超过 n 时，表示已遍历完序列if (u == n + 1) {// 判断数量和和是否满足条件if (cnt >= 2 && !st[cnt] && sum >= 2 && !st[sum]) {ans++; }return;}// 选择当前数字dfs(u + 1, cnt + 1, sum + a[u]); // 选择当前数字，增加个数和和// 不选择当前数字dfs(u + 1, cnt, sum); // 不选择当前数字，保持不变
}int main() {cin >> n; get_primes(N); // 获取所有素数for (int i = 1; i <= n; i++) {cin >> a[i]; }dfs(1, 0, 0); // 从第一个数字开始DFScout << ans; return 0;
}

魔法阵的能量

魔法阵的能量

#include <bits/stdc++.h>
using namespace std;/*思路说明（以代码注释形式呈现）：1. 先读取输入 n，然后判断 n 是奇数还是偶数。如果 n 是奇数 (n & 1)，则直接输出 0 并返回。原因是通过该实现的逻辑认为，如果 n 为奇数，则没有充分的 2 的因子来与 5 配对形成末尾零。2. 如果 n 是偶数，将 ans 设为 n/10，表示在此实现中，先简单认为除以 10 得到其中 2 的数量（实际上并不精准匹配题意，但这是此代码的做法）。然后再将 n 减少 10 倍（n /= 10）。3. 循环中使用 e=5，每次将 e *= 5，不断统计 n/e，累加到 ans 中，试图统计 5 的因子总数。这种统计 5 的方法类似于统计 n! 里 5 的因子个数的方法。4. 最终打印 ans，作为末尾零的数量。*/signed main() {long long n;cin >> n;// 如果 n 是奇数，直接返回 0if (n & 1) {cout << 0 << '\n';return 0;}// 将 n 除以 10，试图统计其中的 2 的数量long long ans = n / 10;n /= 10;// 统计 5 的数量long long e = 5;while (e <= n) {ans += n / e;e *= 5;}// 最终打印累加值 anscout << ans << '\n';return 0;
}

阿坤老师切割年糕

阿坤老师切割年糕

解题思路
大致题意：给定一个整数n,把n分为两个整数，如果这两个整数存在一个是另一个的因数，输出加1，求n中有多少个这样的输出一般思路 ：n为输入的值x + (n-x) = n(n-x) % x == 0时计数器加1可行但时间复杂度大枚举因数 ：由题意x + y =n 已知x是y的因数 即c * x = y, c为大于0的任意常数则x + y = x + c*x = x(c + 1 ) = = n枚举x一个数的因数只用遍历到此数的开根号，例如100，只需遍历1~10，这样就可以大大提升效率，具体原理就自己百度一下；如果n % x == 0, 即存在一个整数c + 1 使（c +1）* x = n, 结果加2为什么加2，当n%x == 0时，x是n的因数，n/x也是n的因数例如n=4时，x的实际范围是1~2，当x=1时，4%1 = 0,4/1=4,1和4都是n的因数 所以加2如果n // x = x,结果加1（因为两个数是一样的，加1即可）当x=2时，x=n/x=2,加1即可最后，我们会发现因数不能等于n,例如x=4时，1+4=5已经大于n了，故cnt要减1

#include <bits/stdc++.h>
using namespace std;int main()
{int n;cin>>n;int cnt=0;for(int i=1;i<=n/i;i++){if(n%i==0){if(n/i==i){cnt+=1;}else {cnt+=2;}}}cout<<cnt-1;return 0;
}

阶乘分解

阶乘分解

阶乘的约数和

阶乘的约数和

#include <bits/stdc++.h>
using namespace std;const int mod = 998244353; // 模数// 定义一个全局 map，用于存储质因数及其对应的次数
map<int, long long> mp;// 对整数 x 进行质因数分解，并将其质因数及对应的次数存入 mp 中
void solve(int x) {for (int i = 2; i <= x / i; i++) {int cnt = 0; while (x % i == 0) { // 如果 i 是 x 的一个因子cnt++;x /= i; }if (cnt) mp[i] += cnt; // 如果 i 是质因数，记录其次数}// 如果 x 本身是一个大于 1 的质数if (x > 1) mp[x]++;
}int main() {int n;cin >> n; // 对 2 到 n 的所有整数进行质因数分解for (int i = 2; i <= n; i++) solve(i);long long sum = 1; // 用于存储约数之和的结果// 遍历所有质因数及其次数for (auto& [p, c] : mp) {long long ret = 0, t = 1;// 计算当前质因数 p 的约数和部分 (1 + p + p^2 + ... + p^c) % modfor (int i = 0; i <= c; i++) {ret = (ret + t) % mod; // 累加当前项t = t * p % mod; // 计算下一项 (p^i)}// 将当前质因数的约数和乘入结果sum = sum * ret % mod;}cout << sum << endl;return 0;
}

程序的输出零

程序的输出零

#include <bits/stdc++.h>
using namespace std;int main() {int n, res = 0;cin >> n;// 思路：需要计算f(n)的末尾有多少个零。// 尾数为0的数字来源于因子2和5的乘积，且因子5的数量通常比因子2少。// 所以，我们主要计算f(n)中因子5的数量。// 由于f(n) = n * f(n-2)，相当于每隔2个数乘一次，只考虑偶数情况。if (n % 2 == 0) { // 如果n是偶数for (int i = n; i > 1; i = i - 2) { // 从n开始每隔2个数递减int temp = i;while (temp % 5 == 0) { // 计算当前数中包含多少个因子5res++; // 每找到一个因子5，结果加1temp /= 5; // 除以5继续检查}}}cout << res << endl; // 输出结果return 0;
}

双子数

双子数

#include <iostream>
using namespace std;
const int N = 4e6 + 10;int primes[N], cnt; 
bool st[N];        void get_primes(int n) {for (int i = 2; i <= n; i++) {if (!st[i]) primes[cnt++] = i;for (int j = 0; primes[j] <= n / i; j++) {st[primes[j] * i] = true; if (i % primes[j] == 0) break;}}
}int main() {int ans = 0;get_primes(N); // 获取所有小于等于N的素数// 遍历所有素数对(p, q)for (int i = 0; i < cnt; i++) {for (int j = 0; j < i && 1LL * primes[i] * primes[j] * primes[i] * primes[j] <= 23333333333333LL; j++) {// 检查p和q的乘积是否在给定范围内if (1LL * primes[i] * primes[j] * primes[i] * primes[j] >= 2333) {++ans; }}}cout << ans; // 输出结果return 0;
}

躲炮弹

躲炮弹

#include <bits/stdc++.h>
using namespace std;
using ll=long long;int n,L,R;
int ans;bool check(int x)// 枚举x的所有因数
{for(int i=1;i<=x/i;i++){if(x%i==0){if(L<=i&&i<=R)return true;// 如果因数i或x/i在[L, R]范围内，则返回trueif(L<=x/i&&x/i<=R)return true;}}// 如果没有因数在[L, R]范围内，则返回falsereturn false;
}
int main()
{cin>>n>>L>>R;// 如果初始位置n在[L, R]范围内if(L<=n&&n<=R){int ans = n - L + 1; // 初始位置到L的距离for(int i=1;i<=2000;i++) // 枚举从R开始向右最多2000步的距离，寻找一个合法位置{if(!check(R+i)){ans=min(ans,R+i-n);// 更新最小步数break;}}cout<<ans<<endl;return 0;}else // 如果初始位置n不在[L, R]范围内{ // 枚举从n向左右最多2000步的距离，寻找一个合法位置for(int i=0;i<=2000;i++){if(!check(n+i)||!check(n-i)){cout<<i<<endl;break;}}}return 0;
}