Đề bài: $\href{https://codeforces.com/problemset/problem/735/D}{Đây}$
Tóm tắt: Cho một số n. Hãy tìm cách tách n thành tổng của hạng tử, sao cho tổng của ước lớn nhất (trừ hạng tử đó là nhỏ nhất)
Lời giải:
+ Nếu n là số nguyên tố thì đáp án là 1
+ Nếu n là số lẻ và n-2 là hợp số thì đáp án là 3
+ Còn lại đáp án là 2.
Source:
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- bool check(ll n){
- if(n==1) return false;
- if(n==2||n==3) return true;
- for (ll i=2;i<=sqrt(n);i++){
- if(n%i==0) return false;
- }
- return true;
- }
- int main(){
- ll n;
- cin>>n;
- if(check(n)){cout<<1; return 0;}
- if(n&1&&!check(n-2)) {cout<<3; return 0;}
- else cout<<2;
- return 0;
- }
Không có nhận xét nào:
Đăng nhận xét