首页 > 代码库 > codeforces 735D Taxes(数论)

codeforces 735D Taxes(数论)

Maximal GCD

题目链接:http://codeforces.com/problemset/problem/735/D

    ——每天在线,欢迎留言谈论。

题目大意:

给你一个n(2≤n≤2e9) 代表一个人的收入。

他需要交税,规则:交税金额为n的最大公约数(本身不算)

他想通过把钱分成几份,然后分别交税,达到交税最少。

知识点:

哥德巴赫猜想:①如果一个数为偶数,那么可以拆成两个质数相加

②如果一个奇数 (n-2)为质数那么他也可以拆成两个质数相加(2+(n-2))

③其他的奇数 可以拆成一个 质素+一个偶数  也就是 3个质数相加

 

思路:

知道这个数论知识就很好做了。

AC代码:

 1 #include <iostream>
 2 #include <cmath>
 3 using namespace std;
 4 typedef long long ll;
 5 bool iszs(ll n)
 6 {
 7     ll b=sqrt(n);
 8     for(int i=2;i<=b;i++)
 9     {
10         if(n%i==0)
11             return false;
12     }
13     return true;
14 }
15 int main()
16 {
17     ll n;
18     cin>>n;
19     if(iszs(n))
20     {
21         cout<<"1"<<endl;return 0;
22     }
23     if(n&1)
24     {
25         if(iszs(n-2))
26         {
27             cout<<"2"<<endl;return 0;
28         }
29         cout<<"3"<<endl;return 0;
30     }
31     else
32         cout<<"2"<<endl;
33     return 0;
34 }

2017-05-28 16:45:27

codeforces 735D Taxes(数论)