Iacob Tudor (IacobTudor) Cerința
Aveți la dispoziție toate numerele naturale de la 1...M pentru a forma vectori de lungime N. De exemplu , Pentru N = 3 și M = 200 , un posibil vector este [199 , 41 , 41]. Pentru fiecare vector distinct care poate fi creat ( doi vectori A și B sunt distincți dacă există cel puțin un i astfel încât A[i] != B[i]) , se cere să determinați cel mai mare divizor comun al elementelor sale. Care este suma valorilor determinate ?
Date de intrare
Inputul conține pe prima linie două numere naturale N și M cu semnificația din enunț.
Date de ieșire
Outputul conține răspunsul cerut modulo 666013.
Restricții și precizări
N <= 1.000.000.000 , M <= 1.000.000.- Pentru teste în valoare de
20 puncte N <= 6 si M <= 8. - Pentru alte teste în valoare de
40 puncte , N <= 100000 si M <= 100 - Pentru restul de
40 punctese respectă restricțiile inițiale.
Exemplu:
Intrare
2 3
Ieșire
12
Intrare
300 100
Ieșire
44076
Explicație
În primul exemplu , vectorii de lungime 2 formați cu elementele din invervalul 1...3 sunt : [1 , 1] , [1 , 2] , [1 , 3] , [2 ,1] , [2 , 2] , [2 , 3] , [3 , 1] , [3 , 2] , [3 , 3]. Suma care trebuie calculată este : gcd(1 , 1) + gcd(1 , 2) + gcd(1 , 3) + gcd(2 , 1) + gcd(2 , 2) + gcd(2 , 3) + gcd(3 , 1) + gcd(3 , 2) + gcd(3 , 3) = 1+1+1+1+2+1+1+1+3 = 12 , unde cu gcd(a , b) s-a notat cel mai mare divizor comun al lui a și b.