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

【数学推导】HDU-1719 Friend

程序员文章站 2024-03-18 09:55:40
...

【数学推导】HDU-1719 Friend

注解

1、数学推导题。设n是一个友好数,那么n就可以分解为:

n = ab + a + b = (a+1)(b+1) - 1,即n+1 = (a+1)*(b+1)由递归定义,这里的a和b也必须是友好数。

a = a1b1 + a1 + b1 = (a1+1)(b1+1) - 1,即a + 1 = (a1+1)(b1+1),同理b + 1 = (a2+1)(b2+1)。

代入n + 1 = (a+1)(b+1)中得到:n + 1 = (a1+1)(b1+1)(a2+1)(b2+1)。而且如果只要ai和bi都不

为1或2,就可以一直分解下去。最终得到n + 1 = (1 + 1)^x * (2 + 1)^y = 2^x * 3^y。

2、有了公式,就有了简单做法:先将n加上1,然后将所有2的素因子和3的素因子全部消去,如果消去因子后得到结果为

1,则说明n+1中只含有2和3的因子,则n为友好数。如果消去因子后结果不为1,即n中还含有其他因子,则n不是友好数。

代码

#include <iostream>

using namespace std;

int main() {

    int n;
    while(cin>>n) {
        if(n) {
            n += 1;
            while(n%2==0) {
                n /= 2;
            }
            while(n%3==0) {
                n /= 3;
            }
            if(n==1) {
                cout<<"YES!"<<endl;
            } else {
                cout<<"NO!"<<endl;
            }
        } else {
            cout<<"NO!"<<endl;
        }

    }

    return 0;
}

结果

【数学推导】HDU-1719 Friend

相关标签: 数学推导