欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2018HDU多校赛-6322D - Problem D. Euler Function【找规律】

程序员文章站 2022-04-03 08:13:25
...

In number theory, Euler’s totient function φ(n) counts the positive integers up to a given integer n that are relatively prime to n. It can be defined more formally as the number of integers k in the range 1≤k≤n for which the greatest common divisor gcd(n,k) is equal to 1.
For example, φ(9)=6 because 1,2,4,5,7 and 8 are coprime with 9. As another example, φ(1)=1 since for n=1 the only integer in the range from 1 to n is 1 itself, and gcd(1,1)=1.
A composite number is a positive integer that can be formed by multiplying together two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor other than 1 and itself. So obviously 1 and all prime numbers are not composite number.
In this problem, given integer k, your task is to find the k-th smallest positive integer n, that φ(n) is a composite number.

Input
The first line of the input contains an integer T(1≤T≤100000), denoting the number of test cases.
In each test case, there is only one integer k(1≤k≤109)
.
Output
For each test case, print a single line containing an integer, denoting the answer.
Sample Input

2
1
2

Sample Output

5
7

题意:φ(n)等于gcd(n,k) ==1的个数,其中k=1,2…n.题目要求的是φ(n)不是质数。 输入是k,输出第k个满足φ(n)不是质数的n。

题解:其实这题就是找规律。我先在纸上算,发现了一个规律,但不确定,就写了一个代码验证一下我找的规律,具体代码如下:

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=1;
int gcd(int a,int b){
    if(a<b) swap(a,b);
    if(b) return  gcd(b,a%b);
    return a;
}

int not_prime(int n){
    int i,flag=0;
    for(i=2;i<=sqrt(n);i++){
        if(n%i==0){
        flag=1; 
        break;
        }   
    }
    if(flag&&n!=1)
    return 1;
    else 
    return 0;
}
int main(void){
    int T;
    scanf("%d",&T);
    while(T--){
        int k;
        scanf("%d",&k);

        for(int j=1;j<50;j++){
            int ans=0;
           for(int i=1;i<=j-1;i++){
            if(gcd(j,i)==1){
                ans++;
            }
        }
        if(not_prime(ans))
        cout<<j<<" ";   
        }   
    }
    return 0;
}

运行结果

1
1
5 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

为了保证准确性,便多次改了for循环中的循环条件,然后确定就敲了代码,具体如下

AC:

#include<iostream>
using namespace std;
int main(void){
    int T;
    scanf("%d",&T);
    while(T--){
        int k;
        scanf("%d",&k);
        if(k==1)
        cout<<"5"<<endl;
        else
        cout<<k+5<<endl;
    }
    return 0;
}
相关标签: 规律