【CodeChef】Chef and Interview
发布时间
阅读量：
阅读量
该程序生成一个质数表并用于快速分解整数 n 为质因数的乘积形式。具体步骤如下：
生成质数表：使用埃拉托斯特尼筛法生成不超过 10^5 的所有质数。
分解整数：对于给定的整数 n ，将其分解为所有可能的子集形式。
计算乘积和：对于每个子集形式（即不同指数组合），计算其元素乘积之和。
输出结果：对每个测试用例输出所有可能子集形式的所有元素乘积之和的结果。
该程序通过预处理质因数分解效率较高，并能够快速处理多个测试用例。
#include<bits/stdc++.h>
using namespace std;
int T;long long n;const int upbound = 100010;
int prime[upbound],tot;bool vis[upbound];
long long ans = 0;
void getprime()
{
vis[0]=vis[1]=true;
for(int i=2;i<=upbound;i++)
{
if(!vis[i])prime[++tot]=i;
for(int j=1;j<=tot&&prime[j]<=upbound/i;j++)
{
vis[i*prime[j]]=true;
if(i%prime[j])break;
}
}
}
int e[upbound],tab[upbound],cnt;
long long mul[upbound];
int main()
{
getprime();
scanf("%d",&T);
while(T--)
{
scanf("%lld",&n);
memset(e,0,sizeof(e));
memset(mul,0,sizeof(mul));
int tmp = n;cnt = 0;
for(int i=1;i<=tot;i++)
{
if(tmp%prime[i]==0)tab[++cnt]=i;
while(tmp%prime[i]==0)
{
tmp/=prime[i];
e[i]++;
}
if(tmp==1)break;
}
for(int i=1;i<=cnt;i++)
{
long long sum = 1;
for(int j=0;j<=e[tab[i]];j++)
{
mul[i]+=sum;
sum*=prime[tab[i]];
}
}
ans = 1;
for(int i=1;i<=cnt;i++)ans*=mul[i];
printf("%lld\n",ans);
}
return 0;
}全部评论 (0)
还没有任何评论哟~