Question

Cerința
Se dau n și k numere naturale. Calculați suma resturilor împărțirii tuturor numerelor naturale de la 1 la n prin numărul k.

Date de intrare
Programul citește de la tastatură numerele n și k, separate prin spațiu.

Date de ieșire
Programul va afișa pe ecran numărul S, reprezentând suma resturilor împărțirii tuturor numerelor naturale de la 1 la n prin numărul k.

Restricții și precizări
1 ≤ n , k ≤ 2.000.000.000

Exemplu
Intrare

7 4
Ieșire

12
Explicație
Împărțind numerele de la 1 la 7 prin 4 obținem resturile: 1,2,3,0,1,2,3. Suma lor este 12.

Ce am gresit la programul meu, in formula, ca i-au 80pcte pe pbinfo?!
#include

using namespace std;

unsigned long long n,k,S,r;

int main ()

{

cin >> n >> k;

if(n<=k) S+=k*(k-1)/2;
else
{
if(n%k==0) r=n/k;
else r=n/k+1;
S=(r-1)*(k*(k-1)/2);
if(n%k==0) S+=k*(k-1)/2;
else S+=(n%k)*(n%k+1)/2;

}

cout << S;

return 0;
}

Numi scrieti programe de 100pcte!!!! Vor fi raportate!!! Trebuie sami stiu greseala.

Answer 1

#include <iostream>
using namespace std;

/*am folosit o formula directa pentru calcul
  prima parte este: (n / k) * (k * (k - 1) / 2). Noi stim ca resturile progreseaza de la 0 la k - 1, astfel daca ar fi sa calculam suma tuturor acestor resturi, ar fi 0 + 1 + 2 + ... + (k - 1) = k * (k - 1) / 2 (Suma Gauss). Stim ca aceasta secventa completa de resturi apare de n / k ori

A doua parte a formulei este (n % k) * (n % k + 1) / 2 , care calculeaza suma resturilor ramase. Aceasta formula provine tot de la suma Gauss.
*/
int main()
{
   int n,k;
   cin>>n>>k;
   cout<<(n/k)*(k*(k-1)/2)+(n%k)*(n%k+1)/2;
}