链接:https://ac.nowcoder.com/acm/contest/635/D
来源:牛客网 D.绕圈游戏 433为了帮ddd提升智商,决定陪他van特殊的游戏。433给定一个带有n个点的环,游戏从1号点开始,433选择任意一个K值(1<=K<=n),意味着ddd可以每次前进K个单位,当ddd再次到达1号点时游戏结束。智商为负数的ddd并不觉得这有什么难度,这时433一脸坏笑的告诉ddd,游戏的真正目的是:有任意K,满足1<=K<=n,求从开始到结束的所有情况的点数和。例如n=6,k=4时,ddd会经过1->5->3->1,那么点数和为1+5+3=9。请注意最后一个点不必算入其中。但是ddd要求出K等于(1-n)的所有情况,433补充道:“不需要重复的点数和,需要升序输出。比如n=6,k=2时,1->3->5->1,sum=9;n=6,k=4时,1->5->3->1,sum=9,像这样重复出现的点数和就不必重复输出了。”ddd智商不够,头都快想秃了,请你来帮帮他。 输入描述: 输入一个整数n(2≤n≤109),代表游戏中一个环的点数。 输出描述: 按照升序输出所有点数和的情况。
示例1
输入
复制6 输出
复制1 5 9 21
示例2
输入
复制16 输出
复制1 10 28 64 136
智障了,以前写过类似的,以为是找素因子,最后发现是智障找因数。。。代码:
1 //D
2 #include<bits/stdc++.h>
3 using namespace std;
4 typedef long long ll;
5 const int maxn=2e7+10;
6 const int maxm=100+10;
7 #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
8
9 //bitset<maxn> is_prime;
10 //int p[maxn],h=0;
11 //
12 //void Prime(int n)
13 //{
14 // is_prime[0]=1;
15 // is_prime[1]=1;
16 // for(int i=2;i<=n;++i){
17 // if(is_prime[i]==0)
18 // p[++h]=i;
19 // for(int j=1;j<=h&&p[j]*i<=n;++j){
20 // is_prime[i*p[j]]=1;
21 // if(i%p[j]==0)
22 // break;
23 // }
24 // }
25 //}
26
27 ll p[maxn];
28 int h=0;
29
30 void init(int n)
31 {
32 int x=sqrt(n);
33 for(int i=1;i<=x;i++){
34 if(n%i==0){
35 p[++h]=i;
36 if(n/i!=i) p[++h]=n/i;
37 }
38 }
39 }
40
41 set<ll> ans;
42
43 int main()
44 {
45 int n;
46 scanf("%d",&n);
47 init(n);
48 // Prime(n);
49 // if(n%2==0) ans[++l]=n/2*(n+1);
50 // else ans[++l]=(n+1)/2*n;
51 for(int i=1;i<=h;i++){
52 // if(n%p[i]!=0) continue;
53 // cout<<p[i]<<endl;
54 int x=(n-1)/p[i]+1;
55 ll sum=x+(ll)x*(x-1)/2*p[i];
56 // cout<<sum<<" "<<p[i]<<endl;
57 ans.insert(sum);
58 }
59 // sort(ans+1,ans+1+l);
60 // cout<<1<<" ";
61 // for(int i=1;i<=l;i++){
62 // if(i!=l) cout<<ans[i]<<" ";
63 // else cout<<ans[i]<<endl;
64 // }
65 // return 0;
66 for(auto it:ans){
67 cout<<it<<" ";
68 }
69 }
|