Simple Pyramid(Progক্রিয়া কনটেস্ট)

OVISLARSUM - Large Sum

Editorial of Problem C- Large Sum

Topics: Big Multiple, Modular Inverse

আপনার যদি এই টপিকসদ্বয় জানা থাকে, তাহলে editorial টা দেখতে পারেন।

আমাদের মূলত ২টা কাজ, b পর্যন্ত যোগফল বের করা, a-1 পর্যন্ত যোগফল বের করা, তারপর subtract করে দেওয়া। আর মাঝখানে কিছু মড্যুলাস করতে হবে। তাহলে আমরা b পর্যন্ত যোগফল বের করা শুরু করি।

ধরেন, আপনাকে 37 পর্যন্ত যোগফল করতে হবে, কিন্তু mod দেওয়া আছে 5.

তাহলে আমার প্যাটার্ন টা এরকম হবে,

ধরেন, আপনাকে 37 পর্যন্ত যোগফল করতে হবে, কিন্তু mod দেওয়া আছে 5.
তাহলে আমার প্যাটার্ন টা এরকম হবে,

1 %5 = 1
2 %5 = 2
3 %5 = 3
4 %5 = 4
5 %5 = 0

6 %5 = 1
7 %5 = 2
8 %5 = 3
9 %5 = 4
10 %5 = 0
.
.
31 %5 = 1
32 %5 = 2
33 %5 = 3
34 %5 = 4
35 %5 = 0
.
36 %5 = 1
37 %5 = 2

.এখানে একটা প্যাটার্ন আসতেছে
1 + 2 +3 +4 +0
1 + 2 +3 +4 +0
1 + 2 +3 +4 +0
1 + 2 +3 +4 +0
1 + 2 +3 +4 +0
1 + 2 +3 +4 +0
1 + 2 +3 +4 +0
1+2

এখন আমি যদি 37 কে 5 দিয়ে ভাগ দেই, তাহলে পাব 7, মানে এই প্যাটার্ন টা 7 বার আসবে। প্রত্যেক টা প্যটার্নের যোগফল হবে
res = (mod*(mod-1))/2.
তাহলে সবগুলো প্যাটার্নের যোগফল হবে,

fres = (mod/n)*res

কিন্তু 7 বার প্যাটার্নের যোগফল বের করা মানে, 35 পর্যন্ত  বের করা,  বাকি সংখ্যাগুলোর জন্য আমাদের ক্যালকুলেট করতে হবে,

 temp = n%mod

 sres = temp*(temp+1))/2

এখন আমাদের fres এবং sres যোগ করে দিলেই আমরা টোটাল যোগফল পেয়ে যাবো। এতটুকুতেই আমাদের রেজাল্ট চলে আসার কথা, যেহেতু ইনপুট অনেক বিশাল হতে পারে, আবার 10^9+7 দিয়ে মড্যুলাস করতে হবে। এখন কাজ হচ্ছে আমরা যেই গুনফল গুলো বের করতেছি, এগুলো bigMultiple ব্যবহার করে করা। ভুলেও *, এই চিহৃ দিয়ে করা যাবে না। আরেকটা কাজ হচ্ছে 2 দিয়ে ভাগ না করে এটার মড্যুলার ইনভার্স বের করে গুন করে দেওয়া। 

.

প্রয়োজনে আমার কোডটা দেখা যেতে পারে, শুধু বুঝার জন্য। কিন্তু টপিকসগুলো না জেনে থাকলে, আগে ভালোভাবে টপিকসগুলো শিখতে হবে।