来总结一下做第一题的思路吧
先贴题目
Problem A: zbj的糖果
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 101 Solved: 12
[Submit][Status][Web Board]
Description
现在zbj跟n个小朋友在玩一个游戏。首先,这n个小朋友的编号分别为1,2,3…n,每个小朋友手里都有不同数量的糖果,每个小朋友手里的糖果数量刚好等于他们的编号。
现在他们按顺序围着一张桌子坐下,即 x 的两边分别坐的是x – 1 和 x + 1,n 和 1 相邻。
现在zbj可以从编号为1的小朋友开始,把他们手里的糖果拿走,当然为了游戏乐趣,对于每一轮游戏,zbj决定规定一个数字 k ,表示他每隔 k 个小朋友,就会拿走当前小朋友手里的糖果,当某次又要拿走编号为 1 的小朋友手里的糖果时,他就会停止这轮游戏。
比如有6个小朋友,规定k为4,即n=6,k=4,zbj拿糖果的顺序为:1→5→3→1
现在zbj想知道,按照这样的游戏规则,最多能拿到手的糖果总数有几种不同的情况?
Input
输入只包含一个正整数n(2<=n<=10^9)表示有n个小朋友。
Output
zbj最后能拿到手里的糖果总数的数量集合,按升序输出,两个数字中间用空格隔开,末尾没有空格。
Sample Input
6
Sample Output
1 5 9 21
HINT
对于样例的解释。有以下6种情况
.png)
题目理解:找一下规律就知道,先将所有最小因子求出来,然后列出所有可能的取法
解题代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int coun=0;
ll s[10000];
ll f(int i,int n){
ll sum=0,t;
t=n/i;
sum=t+i*(t-1)*t/2;
return sum;
}
void g(int pr[],int j,int n,ll s[],ll sum){
for(int i=0;i<j;i++){
sum*=pr[i];
if(sum>=n) {break;}
if(n%sum!=0) {sum/=pr[i];continue;}
s[coun++]=f(sum,n);
g(&pr[i],j-i,n,s,sum);
sum/=pr[i];
}
}
int main(){
int pr[10000];
int i,j=0,t,n;
cin>>n;
t=n;
for(i=2;i<=t;i++){
if(t%i==0) {
while(t%i==0&&t) t/=i;
pr[j++]=i;
}
}
/* for(i=0;i<j;i++){
cout<<pr[i]<<" ";
}*/
g(pr,j,n,s,1);
s[coun++]=f(1,n);
s[coun++]=1;
sort(s,s+coun);
cout<<s[0];
for(i=1;i<coun;i++){
cout<<" "<<s[i];
}
cout<<endl;
return 0;
}
有些细节的地方自己以后再来理解一下