InTheBloodHorse

每日一题(50) codeforces 1091C

字数统计: 225阅读时长: 1 min
2019/01/15 Share

题目地址

题意

给一个数组n,代表一个环有n个节点,从1到n,每次可以跳一个步数,比如跳1步的话,经过的点就是 [1,2,3,…,n],跳2步的话,经过的点为 [1,3,5,…]。要求升序输出能跳回起点(1)的步数总和。

思路

  1. 数据集很大,模拟肯定不行
  2. 可以发现 答案序列长度和因数有关,先暴力找出因子,然后根据等差数列求和,得出答案序列

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
vector<long long>v;
int main()
{
int n;
cin >> n;
for(int i=1;i<=sqrt(n);i++){
if(n%i==0){
v.push_back(1LL*i);
if(n/i != i) v.push_back(1LL* (n/i));
}
}
sort(v.begin(),v.end());
for(int i=v.size()-1;i>=0;i--){
int number = n/v[i];
cout << number + v[i]*(number-1)*number/2 << " ";
}
}

原文作者:InTheBloodHorse

原文链接:http://pyking.cn/2019/01/15/每日一题-50-codeforces-1091C/

发表日期:January 15th 2019, 10:21:28 pm

更新日期:January 15th 2019, 10:33:21 pm

版权声明:Have a fun

CATALOG
  1. 1. 题意
  2. 2. 思路