Codeforces 456B. Fedya and Maths Solution

Solve in C++:

hints:

Find value of (1^n + 2^n + 3^n + 4^n ) mod 5

You are given an positive integer n. You have to find the value of (1n +2n + 3n + 4n ) mod 5.
Note : Value of n may be very large of order 1015.
Examples:

Input : n = 4
Output : 4
Explanation : (14 + 24 + 34 + 44)mod 5 = (1+16+81+256)mod 5 = 354 mod 5 = 4

Input : n = 2
Output : 0
Explanation : (12 + 22 + 32 + 42)mod 5 = (1+4+9+16)mod 5 = 30 mod 5 = 0

Basic Approach : If you will solve this question with a very basic approach of finding value of (1n +2n + 3n + 4n ) and then finding its modulo value for 5, you will certainly get your answer but for the larger value of n we must got wrong answer as you will be unable to store value of (1n +2n + 3n + 4n ) properly.
Better and Proper Approach : Before proceeding to solution lets go through some of periodical properties of power of 2, 3 & 4.

• f(n) = 2n is periodical for n = 4 in terms of last digit. i.e. last digit of 2n always repeat for next 4th value of n. (ex: 2, 4, 8, 16, 32, 64…)
• f(n) = 3n is periodical for n = 4 in terms of last digit. i.e. last digit of 3n always repeat for next 4th value of n.(ex: 3, 9, 27, 81, 243, 729…)
• f(n) = 4n is periodical for n = 2 in terms of last digit. i.e. last digit of 4n always repeat for next 2nd value of n.(ex: 4, 16, 64, 256..)
• 1n is going to be 1 always, independent of n.

So, If we will have a close look for periodicity of f(n) = (1n +2n + 3n + 4n ) we will get that its periodicity is also 4 and its last digits occurs as :

• for n = 1, f(n) = 10
• for n = 2, f(n) = 30
• for n = 3, f(n) = 100
• for n = 4, f(n) = 354
• for n = 5, f(n) = 1300

Observing above periodicity we can see that if (n%4==0) result of f(n)%5 is going to be 4 other wise result = 0. So, rather than calculating actual value of f(n) and then obtaining its value with mod 5 we can easily get result only be examine value of n.

For example:

// Program to find value of f(n)%5 #include <bits/stdc++.h> using namespace std;    // function for obtaining remainder int fnMod(int n) {     // calculate res based on value of n     return (n % 4) ? 0 : 4; }    // driver program int main() {     int n = 43;     cout << fnMod(n) << endl;     n = 44;     cout << fnMod(n);     return 0; }

Output:

0
4

1. ///**********ALLAH IS ALMIGHTY************///
2. ///AH Tonmoy
3. ///Department of CSE
4. ///Islamic University,Bangladesh
5. #include<iostream>
6. #include<string>
7. using namespace std;
8. int main()
9. {
10.  
11. string s;
12. long long int a,b,l,v;
13. cin>>s;
14. l=s.size();
15. a=s[l-1];
16. b=s[l-2];
17. v=b*10+a;
18. if(v%4==0)
19. cout<<"4"<<endl;
20. else
21. cout<<"0"<<endl;
22. }