(A * B)%M = ?

Problem:  (A * B)%M এর ভ্যালু কত সেটা বের করতে হবে যেখানে A<=1e18 , B<=1e18 , M<=1e18

Solution: 

খুব ভালোভাবে বোঝা যাচ্ছে যে, ওভারফ্লো ই এই সমস্যার মূল সমস্যা -_-

এখন, একটু ভিন্নভাবে চিন্তা করি প্রব্লেমটাকে। 

x + x + x + x + x = 5x

৫ টা x যোগ করে পাওয়া যোগফল আর x এর সাথে ৫ গুণ করে পাওয়া গুণফল সমান। এটিই এই সমস্যা সমাধানের মূল কনসেপ্ট! 

তার মানে, A*B হচ্ছে,  B সংখ্যাক A এর যোগফল। এখনো মাথায় না ঢুকলে কোড দেখতে পারোঃ

	ll FuN(ll a , ll b , ll m)
	{
	if(b == 1)
	return (a%m);
	ll half = b/2;
	ll ret = FuN(a , half , m)%m;
	if(b%2 == 0)
	return (ret + ret)%m;
	else
	return ((ret + ret)%m + a)%m;
	}

view raw temp.cpp hosted with ❤ by GitHub