给定一系列0到1之间的所有有理数(0 / 1,1 / 1,1 / 2,1 / 3,2 / 3,...,n / d)打印第k个分数
我已经使用了他们的调试器,我的程序输出了他们给出的完全相同的答案,但判断仍然将其标记为不正确 .
我正在使用Euler's totient function找到分母并迭代通过等于1的GCD来找到分子 . 就我在网上找到的而言,这应该足够了 .
任何帮助,将不胜感激 .
#include <iostream>
#include <stdlib.h>
#include <vector>
#include <math.h>
using namespace std;
//Calculate the greatest common divisor of a and b
long long GCD(long long a, long long b){
if (a == 0){
return b;
}
return GCD(b%a, a);
}
int main(){
long long input;
vector <long long> inputVector;
vector <long long> phiValues;
long long totient;
long long total;
int numerator;
int denominator;
while(cin >> input){
if(input == 0){
break;
}
inputVector.push_back(input);
}
// Calculate phi for all integers from 1 to
// 20000 and store them
for(int i = 1; i <= 200000; i++){
long long current = i;
totient = current;
for(long long k = 2; k <= sqrt(i); k++){
if(current % k == 0){
totient -= totient / k;
while(current % k == 0){
current /= k;
}
}
}
if(current > 1){
totient -= totient / current;
}
phiValues.push_back(totient);
}
for(int i = 0; i < inputVector.size(); i++){
long long N = inputVector[i];
total = 1;
for(int j = 0; j <= phiValues.size(); j++){
if(total >= N){
if(N == 1){ //For the case of N = 1
denominator = 1;
}else{
denominator = j;
}
total -= phiValues[j-1];
break;
}
total += phiValues[j];
}
int index = 0;
for(int j = 1; j <= denominator; j++){
if(GCD(j, denominator) == 1){
index++;
if(index == N - total){
numerator = j;
break;
}
}
}
cout << numerator << '/' << denominator << endl;
}
return 0;
}
1 回答
Here @jte表示可以在
O(N*logN)
中实现PHI的计算:我找不到你的代码问题 . 可能是TLE(超出时间限制)问题,因为你应该使用二分搜索来找到分母 . 但是这段代码将被接受: