首页 > 代码库 > Uva10290 - {Sum+=i++} to Reach N
Uva10290 - {Sum+=i++} to Reach N
Problem H
{sum+=i++} to Reach N
Input: standard input
Output: standard output
Memory Limit: 32 MB
All the positive numbers can be expressed as a sum of one, two or more consecutive positive integers. For example 9 can be expressed in three such ways, 2+3+4, 4+5 or 9. Given an integer less than (9*10^14+1) or (9E14 + 1) or (9*1014 +1) you will have to determine in how many ways that number can be expressed as summation of consecutive numbers.
Input
The input file contains less than 1100 lines of input. Each line contains a single integer N (0<=N<= 9E14). Input is terminated by end of file.
Output
For each line of input produce one line of output. This line contains an integer which tells in how many ways N can be expressed as summation of consecutive integers.
Sample Input
9
11
12
Sample Output
3
2
2
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 1e7+10;
typedef long long ll;
bool isPrime[maxn];
vector<int> prime,cnt;
ll n;
void getPrime(){
memset(isPrime,1,sizeof isPrime);
for(int i = 2; i < maxn; i++){
if(isPrime[i]){
prime.push_back(i);
for(int j = i+i; j < maxn; j+=i){
isPrime[j] = 0;
}
}
}
}
void getDigit(){
while(n%2==0) n/=2;
// cout<<n<<endl;
for(int i = 1; i < prime.size()&&n >= prime[i]; i++){
if(n%prime[i]==0){
int t = 0;
while(n%prime[i]==0){
n /= prime[i];
t++;
}
cnt.push_back(t);
}
}
if(n!=1) cnt.push_back(1);
}
int main(){
getPrime();
while(~scanf("%lld",&n)){
cnt.clear();
getDigit();
ll ans = 1;
for(int i = 0; i < cnt.size(); i++) ans *= (cnt[i]+1);
cout<<ans<<endl;
}
return 0;
}
Uva10290 - {Sum+=i++} to Reach N