【数学推导】HDU-1719 Friend
程序员文章站
2024-03-18 09:55:40
...
注解
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;
}
结果
上一篇: 微信小程序将后台数据传给map中的多个markers 用for循环赋值
下一篇: 接口性能指标