(3^n + 2^n)% 10 für große n

Question

Also habe ich eine Nummer N, die maximal 9 Ziffern hat und ich muss die letzte Ziffer von 3^n + 2^n bekommen. Gibt es eine Regel für diese Art von Problem? Der Code den ich bisher habe:

Allerdings, wenn ich dies nutze und n größer als 1000 ist, zeigt es Nan an.

Meine Frage ist: Gibt es eine Regel für ein solches Problem?

Answer 1

Nun, wir wissen, dass (3^n + 2^n) % 10 = ((3^n % 10) + (2^n % 10)) % 10, so können wir Modular Exponentation verwenden, um dies schnell zu lösen.

Die Grundvoraussetzung ist, dass 3^n % 10 = (3 * (3^(n-1) % 10)) % 10

Answer 2

Nun, die einfachste Antwort ist folgende:

3^0 === 1; 
3^1 === 3; 
3^2 === 9; 
3^3 === 7; 
3^4 === 1; 
3^5 === 3; 

So, 3^n hat letzte Ziffer 3, 9, 7 oder 1, bezogen auf N Also, N% 4 == 0 => letzte Ziffer von 3^n ist 1, == 1 => 3, == 2 => 9, == 3 => 7.

Sie können schreiben das gleiche für 2^n:

1, 2, 4, 8, 6, 2, ...

Dieser Zyklus die ganze Zeit wiederholt werden kann, die primäre Regel auszuschließen: letzte Ziffer für 2^n:

N == 0 => 1 
N > 0 => 
    (N - 1) % 4 == 0 => 2 
    (N - 1) % 4 == 1 => 4 
    (N - 1) % 4 == 2 => 8 
    (N - 1) % 4 == 3 => 6 

Nach Sie haben die letzte Ziffer für 3^n und 2^n berechnet, fügen Sie sie einfach zusammen.

Answer 3

Sie können es mathematisch lösen. Schauen wir uns die Sequenz u _{an. N} = 3^n% 10: u = 1, und dann wieder 3, 9, 7 und 1. Es gibt sofort:

u _4k = 1, u _{4k + 1} = 3, u _{4k + 2} = 9, u _{4k + 3} = 7

Jetzt bei v schauen _n = 2 ⁿ% 10: v = 1 und dann 2,4,8,6 und 2 wieder. Es gibt, dass für k> 0:

v _4k = 6, v _{4k + 1} = 2, v _{4k + 2} = 4, v _{4k + 3} = 8

Sie sofort das Ergebnis hat: für N> 1 nur bei N aussehen‘= N% 4, und die Ergebnisse sind jeweils 7, 5, 3, 5

In C++ wird es geben:

#include <fstream> 
using namespace std; 

ifstream fin("input.in"); 
ofstream fout("input.out"); 

int main(){ 

    int n; 
    fin>>n; 

    int result[] = { 7,5,3,5}; 
    fout<<(n == 0) ? 2 : result[n%4]; 
    return 0; 
}