Codeforces 735D Taxes（简单数论）

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

题意：一个人的收入为n他要交的税是n的最大除数，他为了少缴税将n分成k个数n1,n2,n2....nk（k可以为1）所交的税就n1~nk的所有最大约数的和

一道简单的数论题，首先当n为质数是不用分税为1最小，当n为合数是，n为偶数是根据哥德巴赫猜想任意大于2的偶数可以拆成两个质数的和所以最小为

2，n为奇数时由于奇数只能由偶数和奇数组成所以奇数如果拆掉一个2（最小的偶数）剩下的是质数那么n的税就为2，如果不是那么就小就为3.

#include <iostream>

#include <cstring>

#include <cmath>

using namespace std;

int main() {

    int n;

    cin >> n;

    int flag = 0;

    for(int i = 2 ; i <= sqrt(n) ; i++) {

        if(n % i == 0) {

            flag = 1;

            break;

        }

    }

    if(flag == 0) {

        cout << 1 << endl;

    }

    else {

        if(n % 2 == 0) {

            cout << 2 << endl;

        }

        else {

            int gg = n - 2;

            int temp = 0;

            for(int i = 2 ; i <= sqrt(gg) ; i++) {

                if(gg % i == 0) {

                    temp = 1;

                    break;

                }

            }

            if(temp)

                cout << 3 << endl;

            else

                cout << 2 << endl;

        }

    }

    return 0;

}

巴特西

Codeforces 735D Taxes（简单数论）

最新文章

热门文章