3649 - CMMDC 4: Difference between revisions
Tag: visualeditor |
|||
Line 20: | Line 20: | ||
2*3*1 + 3*4*1 +3*2*1 + 4*3*1 = 36. Restul împărțirii numărului 36 la 1.000.000.007 este 36. | 2*3*1 + 3*4*1 +3*2*1 + 4*3*1 = 36. Restul împărțirii numărului 36 la 1.000.000.007 este 36. | ||
<br> | <br> | ||
== Rezolvare == | == Rezolvare == | ||
<syntaxhighlight lang="python" line> | <syntaxhighlight lang="python" line> | ||
def gcd(a, b): | def gcd(a, b): | ||
while b: | |||
a, b = b, a % b | |||
return a | |||
def euler_totient(N): | def euler_totient(N): | ||
phi = [i for i in range(N + 1)] | |||
for i in range(2, N + 1): | |||
if phi[i] == i: # i este prim | |||
for j in range(i, N + 1, i): | |||
phi[j] -= phi[j] // i | |||
return phi | |||
def main(): | def main(): | ||
N = int(input("Introduceți valoarea lui N: ")) | |||
totient = euler_totient(N) | |||
result = 0 | |||
mod = 10**9 + 7 | |||
for p in range(2, N + 1): | |||
for k in range(1, N // p + 1): | |||
a = p * k | |||
b = p * k + 1 | |||
if b > N: | |||
break | |||
c = p | |||
result += a * b * c * totient[p] % mod | |||
result %= mod | |||
print(result) | |||
if __name__ == "__main__": | if __name__ == "__main__": | ||
main() | |||
</syntaxhighlight> | |||
Latest revision as of 16:45, 3 June 2024
Enunt[edit]
Cerinţa[edit]
Dându-se N, determinați valoarea expresiei: a1•b1•c1 + a2•b2•c2 + ... + ak•bk•ck unde (a1,b1,c1), (a2,b2,c2), …, (ak,bk,ck) sunt toate tripletele care îndeplinesc condițiile de mai sus. Întrucât rezultatul poate fi foarte mare, afișați resul împărțirii valorii expresiei la numărul 1.000.000.007.
Date de intrare[edit]
De la tastatură se citește numărul N.
Date de ieșire[edit]
Pe ecran se va afișa un singur număr natural R reprezentând restul împărțirii rezultatului expresiei descrise anterior la numărul 1.000.000.007.
Restricţii şi precizări[edit]
- 1 ≤ n ≤ 1.000.000
Exemplul 1[edit]
- Intrare
4
- Ieșire
36
Explicație[edit]
Tripletele valide sunt: (2, 3, 1), (3, 4, 1), (3, 2, 1), (4, 3, 1).
2*3*1 + 3*4*1 +3*2*1 + 4*3*1 = 36. Restul împărțirii numărului 36 la 1.000.000.007 este 36.
Rezolvare[edit]
<syntaxhighlight lang="python" line> def gcd(a, b):
while b: a, b = b, a % b return a
def euler_totient(N):
phi = [i for i in range(N + 1)] for i in range(2, N + 1): if phi[i] == i: # i este prim for j in range(i, N + 1, i): phi[j] -= phi[j] // i return phi
def main():
N = int(input("Introduceți valoarea lui N: "))
totient = euler_totient(N)
result = 0 mod = 10**9 + 7
for p in range(2, N + 1): for k in range(1, N // p + 1): a = p * k b = p * k + 1 if b > N: break c = p result += a * b * c * totient[p] % mod result %= mod
print(result)
if __name__ == "__main__":
main()
</syntaxhighlight>