HNUSTOJ-1617 Graph（费马数）

谁践踏了优雅 2022-01-10 09:09 192阅读 0赞

## 1617: Graph ##

时间限制: 1 Sec 内存限制: 32 MB  
提交: 31 解决: 5  
\[ [提交][Link 1]\]\[ [状态][Link 2]\]\[ [讨论版][Link 3]\]

## 题目描述 ##

Your task is to judge whether a regular polygon can be drawn only by straightedge and compass.

The length of the straightedge is infinite.

The width of the compass is infinite.

The straightedge does not have scale.

## 输入 ##

There are several test cases. Each test case contains a positive integer n (3<=n<=10^9). The input will be ended by the End Of File.

## 输出 ##

If the regular polygon with n sides can be drawn only by straightedge and compass, output YES in one line, otherwise, output NO in one line.

## 样例输入 ##

3
    4
    5
    6
    7

## 样例输出 ##

YES
    YES
    YES
    YES
    NO

形如![费马数][01000000000000119081531422091_s.gif]的数，*n*≥0。前五个费马数是*F*0=3,*F*1=5,*F*2=17,*F*3=257,*F*4=65537,均为素数。据此,1640年，法国数学家P.de费马猜想*F*n均为素数，1732年，L.欧拉发现 *F*5=641×6700417，故费马猜想不真。到目前为止，只知道以上五个费马数是素数。此外，还证明了48个费马数是复合数。这些复合数可以分成三类：①当*n*=5,6,7时，得到了*F*n的标准分解式；②当*n*=8,9,10,11,12,13,15,16,18,19,21,23,25,26,27,30,32,36,38,39,42,52,55，58，63,73,77,81,117,125,144,150,207,226,228,250,267,268,284,316,452,556,744,1945时，只知道*F**n*的部分素因数；③当*n*=14时，只知道*F*14是复合数，但是它们的任何真因数都不知道。因此，在费马数列中是否有无穷多个素数，或者是否有无穷多个复合数，都是未解决的问题。自从费马猜想被否定后，有人猜想费马数列中只有有限个素数，这一猜想也未解决。还有一个未能证明的猜想：费马数无平方因子。L.J.沃伦于1967年证明了：如果素数*q*满足*q**2*｜*F**n*，则![费马数][01000000000000119081531423885_s.gif]

费马数有一些简单的性质：如①当整数 *k*>0时，有![费马数][01000000000000119081531424915_s.gif]；②设 *n*>0，*F**n* 是素数的充分必要条件是![费马数][01000000000000119081531426074_s.gif]；③设 *n*>1，*F**n*的每一个素因数形如![费马数][01000000000000119081531427124_s.gif]。

1801年,C.F.高斯证明了,当*h*＝![费马数][01000000000000119081531428350_s.gif](0≤*n*1<*n*2<…<*n*s,*s*≥1),*F*nt(*t*=1,2,…,*s*)都是素数时,正*h*边形可用圆规和直尺来作图，可见费马数与平面几何的一些问题有联系。近年来，费马数在数字信号处理中得到应用。例如，费马数变换(FNT),即以费马数给出的数轮变换,在数论变换中最为有用。

#include<iostream>
    #include<cstring>
    #include<cstdio>
     
    using namespace std;
    const int feimap[5] = {
        3, 5, 17, 257, 65537};
     
    bool fun(int x){
        return (!(x & (x - 1))) && x;
    }
    int main(){
        int n;
        while(scanf("%d", &n) == 1){
            for(int i = 0; i < 5; i++) if(n % feimap[i] == 0) n /= feimap[i];
            printf("%s\n", fun(n)?"YES":"NO");
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Pretty9/p/7406698.html

[Link 1]: http://acm.hnust.cn/JudgeOnline/submitpage.php?id=1617
[Link 2]: http://acm.hnust.cn/JudgeOnline/problemstatus.php?id=1617
[Link 3]: http://acm.hnust.cn/JudgeOnline/bbs.php?pid=1617
[01000000000000119081531422091_s.gif]: http://a3.att.hudong.com/91/15/01000000000000119081531422091_s.gif
[01000000000000119081531423885_s.gif]: http://a1.att.hudong.com/85/15/01000000000000119081531423885_s.gif
[01000000000000119081531424915_s.gif]: http://a0.att.hudong.com/15/15/01000000000000119081531424915_s.gif
[01000000000000119081531426074_s.gif]: http://a3.att.hudong.com/74/15/01000000000000119081531426074_s.gif
[01000000000000119081531427124_s.gif]: http://a2.att.hudong.com/24/15/01000000000000119081531427124_s.gif
[01000000000000119081531428350_s.gif]: http://a3.att.hudong.com/50/15/01000000000000119081531428350_s.gif