首页 > ACM题库 > HDU-杭电 > HDU 2854-Central Meridian Number[解题报告]HOJ
2014
02-17

HDU 2854-Central Meridian Number[解题报告]HOJ

Central Meridian Number

问题描述 :

A Central Meridian (ACM) Number N is a positive integer satisfies that given two positive integers A and B, and among A, B and N, we have
N | ((A^2)*B+1) Then N | (A^2+B)
Now, here is a number x, you need to tell me if it is ACM number or not.

输入:

The first line there is a number T (0<T<5000), denoting the test case number.
The following T lines for each line there is a positive number N (0<N<5000) you need to judge.

输出:

The first line there is a number T (0<T<5000), denoting the test case number.
The following T lines for each line there is a positive number N (0<N<5000) you need to judge.

样例输入:

2
3
7

样例输出:

YES
NO

Hint
Hint X | Y means X is a factor of Y, for example 3 | 9; X^2 means X multiplies itself, for example 3^2 = 9; X*Y means X multiplies Y, for example 3*3 = 9.

#include "cstdio"
#include "cstring"

int main()
{
 int x , y ;
 bool flag[5005];
 for ( int i = 1 ; i <= 5000 ; i ++ )
 {
 flag[i] = false ;
 for ( int a = 1 ; a <= 1000 ; a ++ )
 {
 for ( int b = 1 ; b <= 1000 ; b ++ )
 {
 x = a * a * b + 1 ;
 y = a * a + b ;
 if ( x % i == 0 )
 {
 if ( y % i )
 {
 flag[i] = true ;
 break ;
 }
 }
 }
 if ( flag[i] ) break ;
 }
 }
 int T , n ;
 scanf ( "%d" , &T ) ;
 while ( T -- )
 {
 scanf ( "%d" , &n ) ;
 if ( !flag[n] ) puts("YES") ;
 else puts("NO");
 }
 return 0 ;
}