数数（找质因数个数）
题目描述
登录—专业IT笔试面试备考平台_牛客网
运行代码（通过率一半）
#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中）。
- 首先，从用户输入获取
三位出题人（组合数学，快速幂）
题目描述
登录—专业IT笔试面试备考平台_牛客网
运行代码
#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函数，得到最终的分配任务方案数，并输出。
- 读取题目数量
