首页 > 代码库 > Gym 100917C Constant Ratio 数论+暴力
Gym 100917C Constant Ratio 数论+暴力
题目：
Description
standard input/output
Statements
Statements
Given an integer n, find out number of ways to represent it as the sum of two or more integers ai with the next property: ratio ai / ai - 1is the same positive integer for all possible i > 1.
Input
Input consists of one integer n (1 ≤ n ≤ 105).
Output
Print one integer — number of representations.
Sample Input
Input
1
Output
0
Input
5
Output
2
Input
567
Output
21
Hint
In the first sample no such representation exists.
In the second sample there exist two representations:
- 1 1 1 1 1, then q = 1.
- 1 4, then q = 4.
题目大意：给出一个等比数列（至少连个元素）的和n，要求公比q为整数，求满足要求的等比数列的个数。
题目思路：Sn=a1*(1-q^n)/(1-q),枚举q的值，判断a1是否为整数，比较暴力……
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<vector> 5 #include<stdio.h> 6 #include<stdlib.h> 7 #include<queue> 8 #include<math.h> 9 #define INF 0x3f3f3f3f10 #define MAX 100000511 #define Temp 100000000012 13 using namespace std;14 15 int check(long long q,long long n)16 {17 long long a=q;18 int ans=0;19 while(n*(q-1)/(a-1) >= 1)20 {21 if(n*(q-1)%(a-1)==0 && n*(q-1)/(a-1)>=1 && n*(q-1)/(a-1)<n)//判断a1是否为整数，且满足要求22 ans++;23 a*=q;24 }25 return ans;26 }27 28 int main()29 {30 int n,sum;31 sum=0;32 scanf("%d",&n);33 for(int i=1; i<n; i++)34 {35 if(n%i==0 && n/i>1)36 sum++;37 }38 for(int i=2; i<n; i++)//枚举公比的值39 {40 sum+=check(i,n);41 }42 printf("%d\n",sum);43 return 0;44 }
Gym 100917C Constant Ratio 数论+暴力
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。