3649 - CMMDC 4: Difference between revisions

From Bitnami MediaWiki
RebecaBud (talk | contribs)
RebecaBud (talk | contribs)
 
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>
</syntaxhighlight><nowiki><syntaxhighlight lang="python" line></nowiki>
def gcd(a, b):
def gcd(a, b):
 
    while b:
    while b:
        a, b = b, a % b
 
    return a
        a, b = b, a % b
 
    return a


def euler_totient(N):
def euler_totient(N):
 
    phi = [i for i in range(N + 1)]
    phi = [i for i in range(N + 1)]
    for i in range(2, N + 1):
 
        if phi[i] == i: # i este prim
    for i in range(2, N + 1):
            for j in range(i, N + 1, i):
 
                phi[j] -= phi[j] // i
        if phi[i] == i:  # i este prim
    return phi
 
            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: "))


    N = int(input("Introduceți valoarea lui N: "))
    totient = euler_totient(N)


    totient = euler_totient(N)
    result = 0
    mod = 10**9 + 7


    result = 0
    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


    mod = 10**9 + 7
    print(result)
 
    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()


    main()
</syntaxhighlight>
 
<nowiki></syntaxhighlight></nowiki>

Latest revision as of 16:45, 3 June 2024

Enunt[edit | edit source]

Cerinţa[edit | edit source]

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 | edit source]

De la tastatură se citește numărul N.

Date de ieșire[edit | edit source]

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 | edit source]

  • 1 ≤ n ≤ 1.000.000

Exemplul 1[edit | edit source]

Intrare
 4
Ieșire
 36

Explicație[edit | edit source]

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 | edit source]

<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>