HDU 1719 Friend

1160 단어 ACMHDU
제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=1719
친구 num
           a 와 b 가 friend num 이면 a + b + a * b 도 friend num
          
사고방식: a + b + a * b = (a + 1) * (b + 1) - 1
           a=c+d+c*d=(c+1)*(d+1)-1, b=e+f+ef=(e+1)*(f+1)-1
           (a+1)*(b+1)-1=[(c+1)*(d+1)]*[(e+1)*(f+1)-1]-1;
            분할 을 계속 반복 하면 반드시 [(1 + 1) ^ x] * [(2 + 1) ^ y] - 1 이 되 므 로 N + 1 은 2 와 3 을 계속 나 누 어 제거 되 지 않 을 때 까지 1 여 부 를 판단 하면 됩 니 다.
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int main()
{
    int n;
    while (scanf("%d",&n)!=EOF)
    {
        if (n==1 || n==2)
        {
            printf("YES!
"); } else if (n==0) { printf("NO!
"); } else { n+=1; while (n%3==0) n=n/3; while (n%2==0) n=n/2; //cout<<n<<endl; if (n==1) printf("YES!
"); else printf("NO!
"); } } }

좋은 웹페이지 즐겨찾기