ACM_cf#382 Div2 D. Taxes(数论水题
ฅ'ω'ฅ♪

ACM_cf#382 Div2 D. Taxes(数论水题

Codeforces Round #382 (Div. 2) D. Taxes

题目大意:

给出一个n , n可以表示为 一个或多个不为一的数的和式 ,

如果将分解后的数的除数自身外的最大因子相加,问相加结果的最小值。

要求除数自身外的最大因子相加后取min

明显这个数是素数就可了

而我们有

  1. 三素数定理:每个充分大的奇数都是三个奇素数之和。
  2. 强哥德巴赫猜想:任一大于2的偶数都可写成两个素数之和。

但是对于奇数:如果能写成“2+素数”的形式,那么最终ans就不是三素数的“1”而是ans-2了;

所以对于n:

  1. 偶数:
  2. 等于2 ? ans=1 (特判 ) ;
  3. 不等于2 , ans = 2( 1+1 );
  4. 奇数:
  5. 素数 ? ans = 1 ;
  6. n-2是素数?
    1. 是,ans=2 ;
    2. 否,ans=3 ;

简单的代码即可ac。

记得开ll ;

int isPrime(ll n)
{
    float n_sqrt;
    if(n==2 || n==3) return 1;
    if(n%6!=1 && n%6!=5) return 0;
    n_sqrt=floor(sqrt((float)n));
    for( ll i=5;i<=n_sqrt;i+=6 ) if( n%(i)==0 || n%(i+2)==0) return 0;
    return 1 ;
}
signed main()
{
    ll n=read() ;
    if( !(n-2) ) outn(1) ;
    else if( !(n&1) ) outn(2) ;
    else if( isPrime(n) ) outn(1) ;
    else if( isPrime(n-2) ) outn(2) ;
    else outn(3) ;
}
CANCEL

-评论-

Here you can post what you want to say, if you have more information please contact me by the following way.

-昵称-
-QQ-
-邮箱-
想说些什么?
-SUBMIT-

-电联 Phone-

+86 18520664652

-邮箱 Email-

boogieLing_o@163.com

boogieLing_o@qq.com

Your name. OS platform Browser model

What do you want to say?

created time

游說萬乘苦不早,著鞭跨馬涉遠道。

阿凌的貓爬架

幸會,

激活Ubuntu

转到“设置”以激活Ubuntu。

R0's board.