首页 > 代码库 > 7-21测试
7-21测试
问题 A: 挖掘机技术哪家强
时间限制: 1 Sec 内存限制: 128 MB提交: 326 解决: 83
[提交][状态][讨论版]
题目描述
有人问现实中为什么总是男生追求女生，反过来很少。实际上女生也是想主动追求男生的，但是世俗中对于主动追求男生的女生有种歧视，这样就使得女生不大敢主动追求男生。但是面对喜欢的男生，难道就不出手么？女生只能步步为营，挖坑来引诱男生往里跳。这时候问题就来了，挖掘机技术到底哪家强？
被热血沸腾的广告洗脑了若干天后，Matt终于下定决心，毅然登上了开往泉城的列车，决心寻找生活的希望。
来到布鲁谢特学院后，Matt逐渐地了解了各种型号的挖掘机。在这里我们可以认为有大挖掘机和小挖掘机两种。
今天Matt的任务很简单：首先他要用大挖掘机挖出恰好N单位体积的砂土。由于小挖掘机比较笨拙，它每次挖的砂土体积是固定的。也就是说，设每次挖x单位体积砂土，那么N需要被x整除。在挖出若干堆体积为x的砂土后，Matt需要计算x的“难挖指数”。体积x的“难挖指数”定义如下：对于某个不超过x的体积y，如果x与y的最大公约数为1，那我们认为体积y是“难挖的”，x的“难挖指数”就要加上y。
由于Matt之后还需要用小挖掘机处理被大挖掘机挖出的砂土，他希望知道所有可能的x的难挖指数的和，这样他好估算今天要干多久，不然作为布鲁谢特的高才生，他出门要被笑话的。
输入
第一行一个整数T，表示数据组数。
接下来T行每行一个整数表示N。
输出
对于每个数据输出一行一个整数表示难挖指数的和。
样例输入
3234
样例输出
246
提示
题目意思：定义两个函数f，g，并求出g(n)的值：
。
这道题有一个小定理。小于自然数x的所有与x互质的自然数的和为φ(x)*x/2。因为如果a与x互质，x-a必定与x互质。两两配对即可。
所以原题就变为了求所有是n约束的x的x*φ(x)/2之和。
考场时用质因数分解+爆搜实现了一下，因为数据不是特别大水过了。
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; int n,m,num[10005],prime[10005],s[10005]; long long tot,tmp,ans; void calc() { tot=tmp=1; for(int i=1;i<=m;i++) { tot*=s[i]; } if(tot==1) { ans+=1; return; } tmp=tot; for(int i=1;i<=m;i++) if(s[i]!=1) tmp=tmp*(prime[i]-1)/prime[i]; ans+=tmp*tot/2; } void dfs(int x) { if(x>m) { calc(); return; } s[x]=1;dfs(x+1); for(int i=1;i<=num[x];i++) { s[x]*=prime[x]; dfs(x+1); } s[x]=1; } int main() { int T; scanf("%d",&T); while(T--) { m=ans=0; scanf("%d",&n); for(int i=2;i<=sqrt(n);i++) if(n%i==0) { prime[++m]=i; num[m]=0; while(n%i==0) { num[m]++; n/=i; } if(n==1) break; } if(n!=1) prime[++m]=n,num[m]=1; dfs(1); printf("%lld\n",ans); } }
7-21测试
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。