Codeforces735D题解

发表于 | 评论数： | 阅读次数：

终于找到水黑题啦！嘤~

题意概述

某人要交税，交的税钱是收入n的最大因子（$\neq n$，若该数是质数则是1），

但是现在这人为了避税，把钱拆成几份，使交税最少，输出税钱。

INPUT & OUTPUT’s examples

Input’s eg #1

1
27

Output’s eg #1

1
3

分析

当窝看到这个题的时候，脑子里立马蹦出来:这tm不就要利用哥德巴赫猜想吗？

顿时出了一身冷汗，但忍住凉凉的心态把题意看完。

突然发现，这玩意确实有点和高端数学沾边（也就沾一点）。

我们来举个栗子：

当$n=8$时，我们可以把它拆成$3$和$5$，而这两个都是质数，所以显然他们之和为$2$.

通过简单的分析，我们可以得出一些规律：

  • 当$n$为一个质数时，显然答案为1
  • 根据哥德巴赫猜想，如果一个数为偶数，那么一定能够被分为两个质数之和，所以若$n$为偶数，答案为$2$。
  • 剩下了不是质数的奇数，因为奇数-偶数=奇数,所以若$n-2$为一个质数，就输出$2$。
  • 如果以上条件都不符合，那么这个数一定能够被分成$3+$一个偶数，输出$3$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
using namespace std;
namespace input{
    const int BUFSIZE=(1<<20);
    char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
    char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
    inline char getch(){
        if(is==it)
            it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is==it)?EOF:*is++;
    }
    inline int getint(){
        int res=0,neg=0,ch=getch();
        while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
            ch=getch();
        if(ch=='-'){
            neg=1;ch=getch();
        }
        while(isdigit(ch)){
            res=(res<<3)+(res<<1)+(ch-'0');
            ch=getch();
        }  
        return neg?-res:res;
    }
}
using namespace input;
/* definitions */
long long n;
/* functions */
inline bool is_prime(long long num){
	if(num==1||num==0)return false;
	else{
		for(long long i=2;i<=sqrt(num);i++){
			if(num%i==0)return false;
		}
		return true;
	}
}
int main(int argc,char *argv[]){
	scanf("%d",&n);
	if(is_prime(n)){
		printf("1\n");
	}
	else if(n%2==0)printf("2\n");
	else if(is_prime(n-2))printf("2\n"); 
	else printf("3\n");
	return 0;
}

THE END