Euler 160: Znajdź nietrywialne 5 cyfr silniaka

Podając liczbę, znajdź 5 cyfr przed końcowym 0. 9! = 362880 , więc f (9) = 36288 10! = 3628800, więc f (10) = 36288 20! = 2432902008176640000 tak Rf (20) = 17664 Wyszukiwanie f (1,000,000,000,000)Euler 160: Znajdź nietrywialne 5 cyfr silniaka

Do tego zostały obliczone z f(10^6) a następnie f(10^12) = (f(10^6))^(10^6) do obliczania f(n) ... Ja obliczania silni usuwając wszelkie 5 i odpowiadającego 2, tak aby usunąć wszystkie zer końcowe końcowe .
Ale dostaję złą odpowiedź.
Czy jest jakiś problem w podejściu lub jakiś głupi błąd?

Kod odniesienia

long long po(long long n, long long m, long long mod) { 
    if (m == 0) return 1; 
    if (m == 1) return n % mod; 
    long long r = po(n, m/2, mod) % mod; 
    if (m % 2 == 0) return (r * r) % mod; 
    return (((r * r) % mod) * n) % mod; 
} 

void foo() { 
    unsigned long long i, res = 1, m = 1000000 , c = 0, j, res1 = 1, mod; 
    mod = ceil(pow(10, 9)); 
    cout << mod << endl; 
    long long a = 0, a2 = 0, a5 = 0; 
    for (i = 1 ; i <= m; i++) { 
     j = i; 
     while (j % 10 == 0) 
      j /= 10; 
     while (j % 2 == 0) { 
      j /= 2; 
      a2++; 
     } 
     while (j % 5 == 0) { 
      j /= 5; 
      a5++; 
     } 
     res = (res * j) % mod; 
    } 

    a = a2 - a5; 

    for (i = 1; i <= a; i++) 
     res = (res * 2) % mod; 
    for (i = 1; i <= 1000000; i++) { 
     res1 = (res1 * res) % mod; 
    } 
    cout << res1 << endl; 
}

Źródło

2012-02-17 titan

Czy możesz opublikować swój kod? – 0605002

także, nie jest czymś, co powinieneś rozwiązać samemu, niż poprosić o pomoc ... po prostu mówiąc, że jeśli ktoś inny rozwiąże za Ciebie, nie tylko nie uzyskasz z niego nic, ale odpowiedź będzie teraz dostępna TAK, aby wszyscy mogli to zobaczyć. – hackartist

Twój równości f(10^12) = (f(10^6))^(10^6) jest źle. f() opiera się na silnikach, a nie na mocach.

Źródło

2012-02-17 18:57:55

Moje założenie: obliczono 5 ostatnich cyfr (10^6)! teraz wszystkie inne cyfry> 10^6 będą miały te same 5 ostatnich cyfr, z których wyliczyliśmy (10^6)! Tak f (2 * (10^6)) = f (10^6)! * f (10^6) W podobny sposób f (n * 10^6) = (f (10^6))^n – titan

@titan: ale końcowe zera w liczbach oznaczają, że nie można traktować całości moduł problemowy 1000000 w ten sposób. Na przykład 123000 w pierwszym milionu spowoduje dodanie różnych cyfr do woluminu 5 niż 1123000, więc nie są one równoważne. –

swoje założenia są błędne:

F (10^12) nie jest taki sam jak f (10)^6^(10)^6.
w celu uzyskania niskiego rzędu cyfr 0 poza silnikiem, nie wystarczy usunąć wszystkich wielokrotności 10, 2 i 5 z multiplicands. Usunięcie wielokrotności 10 jest dobrym pomysłem, dla 5 i 2, powinieneś usunąć czynnik 2 lub 5 tylko wtedy, gdy druga mnożna jest wielokrotnością odpowiednio 5 i 2.

Należy uprościć kod i obliczyć modulo jakąś moc 10, ale 10^9 wydaje się zbyt wysoka jak 10^9 * 10^12 wyleje 64-bitowy typ unsigned long long.

Źródło

2017-02-13 20:29:24 chqrlie

Euler 160: Znajdź nietrywialne 5 cyfr silniaka

Odpowiedz

Powiązane problemy