当前位置：首页 > news >正文

数论——数数（找质因数个数），三位出题人（组合数学，快速幂）

news 2025/4/30 0:55:44

数数（找质因数个数）

题目描述

运行代码（通过率一半）

#include <iostream>  
#include <vector>  using namespace std;  const int N=5e6+6;
int n;
vector<bool>vis;
void prime(){for(int i=2;i*i<=n;i++){if(!vis[i]){for(int j=i*i;j<=n;j+=i){vis[j]=true;}}}
}
int main(){cin>>n;vis.assign(n+1,false);prime();int ans=0;for(int i=2;i<=n;i++){if(!vis[i]){int t=i;while(t<=n){ans++;t*=i;}}}cout<<n-1-ans;return 0;
}

代码思路

const int N = 5e6 + 6;：定义了一个常量 N，其值为 5000006，可能是为了确保在处理数据时，数组或其他数据结构有足够的空间。
int n;：用于存储用户输入的整数，代表要进行计算的范围上限。
vector<bool> vis;：一个布尔类型的向量，用于标记整数是否为非素数。初始时假设所有的数都是素数（通过 vis.assign(n + 1, false); 将所有元素初始化为 false）。
void prime() 函数：
- 这个函数的作用是筛选出小于等于 n 的非素数。
- 外层循环从 2 开始遍历到 sqrt(n)。对于每个数 i，如果 vis[i] 为 false，说明 i 是素数。
- 内层循环从 i*i 开始，将 i 的倍数标记为非素数（即 vis[j] = true;）。这是因为小于 i*i 的倍数在之前的遍历中已经被标记过了。
int main() 函数：
- 首先，从用户输入读取整数 n。
- 调用 vis.assign(n + 1, false); 初始化 vis 向量，将所有元素初始化为 false，表示初始时都假设所有的数都是素数。
- 调用 prime() 函数进行素数筛选。
- 然后通过一个循环遍历从 2 到 n 的所有整数。对于每个数 i，如果它是素数（即 !vis[i]），则进行以下操作：
  - 定义一个变量 t 并初始化为 i。
  - 通过一个内层循环，不断将 t 乘以 i，并统计以 i 为底数的整数次幂且小于等于 n 的数的个数（每次循环 ans 加一）。
- 最后，输出 n - 1 - ans，其中 n - 1 是因为总数 n 中减去了 1，再减去 ans 是为了去掉既是完全平方数又是某个数的整数次幂的数的个数。

运行代码（正确）

#include <iostream>  
#include <vector>  using namespace std;  const int N=5e6+6;
int n;
vector<bool>vis;
void prime(){for(int i=2;i*i<=n;i++){if(!vis[i]){for(int j=i*i;j<=n;j+=i){vis[j]=true;}}}
}
int main(){cin>>n;vis = vector<bool>(n+1);prime();int ans=0;for(long long i = 2;i<=n;i++){if(!vis[i]){for(long long j = i;j<=n;j*=i)ans++;}}cout<<n-1-ans;return 0;
}

修改了部分代码

for(long long i = 2;i<=n;i++)
{
if(!vis[i])
{
for(long long j = i;j<=n;j*=i)
ans++;
}
}

代码思路

这段代码的目的是计算在 1 到 n 的范围内，减去既是完全平方数又是某个数的整数次幂的数后剩余的数的个数。

prime 函数：
- 这个函数用于筛选出小于等于 n 的所有非素数。
- 它从 2 开始遍历到 sqrt(n)。对于每个未被标记为非素数的数 i，将其倍数（从 i*i 开始，因为小于 i*i 的倍数在之前的遍历中已经被标记过了）标记为非素数。这样在遍历结束后，vis 数组中标记为 false 的位置对应的数就是素数。
main 函数：
- 首先，从用户输入获取 n 的值。
- 初始化 vis 数组为长度 n + 1 的布尔型向量，初始值都为 false，表示初始时都假设所有的数都是素数。
- 调用 prime 函数进行素数筛选。
- 然后通过双重循环来计算满足条件的数的个数。外层循环从 2 遍历到 n，对于每个数 i，如果它是素数（即 !vis[i]），则进入内层循环。内层循环从 i 开始，每次乘以 i，直到超过 n 为止，每次循环都增加 ans 的值。这个过程实际上是在计算以素数 i 为底数的整数次幂且小于等于 n 的数的个数。
- 最后，输出 n - 1 - ans，即 n 减去既是完全平方数又是某个数的整数次幂的数的个数再减去 1（因为 1 也被包含在总数 n 中）。

三位出题人（组合数学，快速幂）

题目描述

运行代码

#include <iostream>
using namespace std;
using ll = long long;
const int N = 1000000007;ll qmi(ll a, ll b) {ll res = 1;while (b) {if (b & 1) res = res * a % N;a = a * a % N;b >>= 1;}return res % N;
}int main() {int t;cin >> t;while (t--) {ll n, m;cin >> n >> m;ll temp = (qmi(2, m) - 2 + N) % N;cout << qmi(temp, n) << endl;}return 0;
}

代码思路

qmi 函数是用来快速计算整数 a 的 b 次幂对 N（这里 N 是 1000000007）取模的结果。
- 通过位运算的技巧，每次将指数 b 右移一位，如果此时 b 的最低位为 1，则将当前结果 res 乘以 a，并对 N 取模。
- 同时，将 a 自乘，也对 N 取模，这样逐步计算出 a 的 b 次幂对 N 的余数。
首先读取测试用例的数量 t。
对于每个测试用例：
- 读取题目数量 n 和人数 m。
- 计算 qmi(2, m)，表示 m 个人，每个人有两种选择（参与某个题目或不参与），那么总共有 2^m 种情况。
- 但是这里要排除两种不合法的情况，即所有人都不参与任何题目和所有人都只参与一个题目（这样不符合每个题都应有至少一个人参与的条件），所以减去 2。由于结果可能为负数，加上 N 确保结果为正数，然后对 N 取模，得到 (qmi(2, m) - 2 + N) % N。
- 最后将这个结果作为新的底数，题目数量 n 作为指数，再次调用 qmi 函数，得到最终的分配任务方案数，并输出。