[Codeforces] 735D. Taxes

題目連結:http://codeforces.com/problemset/problem/735/D
IOICamp的時候有提到這題,不過我其實已經忘了結論了www
去翻了一下才知道原來是跟哥德巴赫猜想有關,其猜想簡而言之就是說對於任意一個大於二的偶數,都可以拆成兩個質數相加。所以我們這題的做法就是先看看給定的數是不是質數,如果是當然就輸出1,接下來看他是不是偶數,是的話那根據歌德巴赫猜想,答案應該會是2,而對於一個奇數,我們要先看看他減二是不是質數,是的話輸出2,不是的話輸出3,因為對於一個奇數他一定是拆成一個質數加一個偶數,然後偶數拆成兩個質數,但要是拆出來的偶數是二,那答案就變成2了。
p.s. 附個維基上哥德巴赫猜想的條目https://zh.wikipedia.org/wiki/哥德巴赫猜想
#include <bits/stdc++.h>
using namespace std;
bool isprime(int n){
	for(int i=2;i*i<=n;i++){
		if(n%i==0) return false;
	}
	return 1;
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n; cin>>n;
	if(isprime(n)) cout<<1<<'\n';
	else if(n%2==0 or isprime(n-2)) cout<<2<<"\n";
	else cout<<3<<'\n';
	return 0;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology