Codeforces round #382, problem 735D/736B - Taxes Solution

Problem Description:

problem link

এক ব্যক্তি তার ইনকাম ট্যাক্স দিবেন । তার ইনকাম n টাকা ।
ট্যাক্স দেবার নিয়ম হলো - যদি x টাকার ট্যাক্স দেন, ট্যাক্স হবে x ছাড়া x এর সবচেয়ে বড় divisor ।
যেমন, তিনি যদি ৬ টাকার ট্যাক্স দেন, তবে তাকে ৩ টাকা ট্যাক্স দিতে হবে, যদি ২৫ টাকার ট্যাক্স দেন, তবে তাকে ৫ টাকা ট্যাক্স দিতে হবে ।
একইভাবে, x=35 হলে, Tax = 7 টাকা

লোকটি একটি বুদ্ধি বের করল, তিনি n টাকার ট্যাক্স একবারে দেবেন না, ভেঙ্গে ভেঙ্গে দেবেন । এমনভাবে দেবেন, যাতে তাকে সর্বনিম্ন Tax দিতে হয় । তবে তিনি ১ টাকার ট্যাক্স দিতে পারবেন না, যেহেতু ১ ছাড়া ১ এর আর কোন Divisor নেই ।

যেমন, তিনি ৩০ টাকার Tax দিতে চাইলে বিভিন্নভাবে দিতে পারেন-
৩০ = ২+২৮, Tax = ১+১৪ = ১৫টাকা
অথবা, ৩০ = ৩+২৭, Tax = ১+৯ = ১০ টাকা
অথবা, ৩০ = ৪+২৬, Tax = ২+১৩ = ১৫ টাকা
অথবা, ৩০ = ৫+২৫, Tax = ৫+৫ = ১০ টাকা

অথবা, ৩০ = ৬+২৪, Tax = ৩+১২ = ১৫ টাকা

অথবা, ৩০ = ৭+২৩, Tax = ১+১ = ২ টাকা
অথবা, ৩০ = ৮+১০+৭+৬, Tax = ৪+৫+১+৩ = ১৩ টাকা
...
...
...

এভাবে, আরো অনেকভাবেই তিনি ট্যাক্স দিতে পারেন ।

মানে একটি সংখ্যাকে তিনি যত ভাবে বিভিন্ন সংখ্যার যোগফল হিসেবে প্রকাশ করতে পারেন, তত উপায়ে ট্যাক্স দিতে পারেন । তার মধ্য যেভাবে ট্যাক্স দিলে, সর্বনিম্ন ট্যাক্স দিতে হবে, তিনি সেইভাবে ট্যাক্স দেবেন ।

এক্ষেত্রে, n = ৩০ এর জন্য, যেহেতু ২ সর্বনিম্ন, তাই সর্বনিম্ন ২ টাকা ট্যাক্স দিবেন ।

তোমাকে বলতে হবে, n টাকার ট্যাক্স দিতে হলে, তিনি সর্বনিম্ন কত টাকা দিতে পারবেন ?

constraint:   2<=n<=2*10^9

অ্যানালাইসিস:

খেয়াল করে দেখ, Prime Number(মৌলিক সংখ্যা) ক্ষেত্রে ঐ সংখ্যা ছাড়া সবচেয়ে বড় Divisor হলো ১ ।

তাই যদি কোন সংখ্যাকে Prime Number এর যোগফল হিসেবে ভেঙ্গে প্রতিটি Prime Number এর জন্য আলাদা ভাবে ট্যাক্স দেন, তবে প্রতিটি Prime Number এর জন্য ১ টাকা করে ট্যাক্স দিতে হবে । সংখ্যাটিকে যত গুলি Prime Number এর যোগফল হিসেবে প্রকাশ করা হবে,  মোট ট্যাক্স হবে তত ।

যেমন ৩০ এর জন্য ৩০ = ৭+২৩, এখানে ৭ ও ২৩Prime Number, তাই ট্যাক্স হবে ১+১ = ২ টাকা ।

এখন এইটা দেখার বিষয়, কোন সংখ্যাকে সর্বনিম্ন কতগুলি Prime Number এর যোগফল হিসেবে প্রকাশ করা যায় । এটিই এই সমস্যার সমাধান ।

তাহলে তুমি কিভাবে করবে?

তোমার মনে হতে পারে n পর্যন্ত Prime Number generate করে নিয়ে, দেখবে n কে সর্বনিম্ন কয়টি Prime Number এর যোগফল হিসেবে প্রকাশ করা যায় ।

কিন্তু এভবে করতে চাইলে, TLE খাবে ।

তাহলে এর চেয়ে সহজ উপায় কি? তুমি একটু চিন্তা করে দেখ তো ! আগে চিন্তা কর, না পারলে নিচের অংশ পড় ।

সমাধান:

কোন সংখ্যা যদি নিজেই Prime Number হয়, তবে তাকে আর ভাংতে হবে না । এক্ষেত্রে ট্যাক্স ১ টাকা ।

এখন খেয়াল কর, Goldbach's conjecture অনুযায়ী "Every even integer greater than 2 can be expressed as the sum of two primes"

তাহলে, যদি n=2 হয়, তবে যেহেতু n prime number, তাই ট্যাক্স হবে ১ টাকা । আর যদি অন্য কোন জোড় সংখ্যা হয়, তবে ট্যাক্স হবে ২ টাকা, যেহেতু বাকি সব জোড় সংখ্যাকেই দুইটি prime number এর যোগফল হিসেবে প্রকাশ করা যাবেই ।

তাহলে জোড় সংখ্যার জন্য সমাধান পেয়ে গেলাম ।

বিজোড় সংখ্যার জন্য সমাধান কি? একটু চিন্তা করে দেখ। না পারলে, নিচের অংশ দেখ ।

Goldbach's weak conjecture অনুযায়ী, "Every odd number greater than 5 can be expressed as the sum of three primes."

সমাধান তো পেয়ে গেলে !

এইটুকু পড়েই যদি সাবমিট করে থাক, তাহলে এতক্ষণে নিশ্চয় WA খেয়ে মাথা চুলকাচ্ছ !!

বিজোড় সংখ্যাকে ৩ টা প্রাইম নাম্বারের যোগফল হিসেবে প্রকাশ করা যায় ঠিকই, কিন্তু কখনো যদি দুইটি প্রাইম নাম্বারের যোগফল হিসেবে প্রকাশ করা যায়, তবে ?

যেমন, ১৫ কে ২+১৩ আকারে লেখা যায়। তাহলে ট্যাক্স হবে ২ টাকা ।

তাহলে কখন একটি বিজোড় সংখ্যাকে দুইটি প্রাইম নাম্বারের যোগফল হিসেবে প্রকাশ করা যাবে ?

২ ছাড়া অন্য দুইটি প্রাইম নাম্বারের যোগফল হিসেবে কখনোই প্রকাশ করা যাবে না । কারণ দুইটি বিজোড় সংখ্যার যোগফল কখনোই বিজোড় হবে না ।

তাই একটি ২ হতে হবেই । বাকি থাকল n-2 । এখন দেখতে হবে n-2 প্রাইম কিনা । যদি হয়, তাহলে সম্ভব ।

অর্থাৎ, যদি n বিজোড় হয় এবং n-2 প্রাইম হয়, তাহলেই কেবল মাত্র একটি বিজোড় সংখ্যাকে দুইটি প্রাইম নাম্বারের যোগফল হিসেবে প্রকাশ করা যাবে ।

এই হলো প্রোবলেমটির সমাধান !!

কোড:

	//solution of CF 735D/736B
	//Category: Number Theory
	#include<bits/stdc++.h>
	using namespace std;
	bool isPrime(int n)
	{
	for(int i=2;i<=n/i;i++)
	if(n%i==0)
	return 0;
	return 1;
	}
	int main()
	{
	int n;
	cin>>n;
	if(n==2)
	cout << "1\n";
	else if(n%2==0)
	cout << "2\n";
	else if(isPrime(n))
	cout << "1\n";
	else if(isPrime(n-2))
	cout << "2\n";
	else cout << "3\n";
	return 0;
	}

view raw cf 735d.cpp hosted with ❤ by GitHub