Problem 12: Modulus

Points:

Small Case: 5 Answer: 99999307

Large Case: 10 Answer: 80397263

Given the values of M and N, find (0 mod M + N mod M + 2N mod M +...+ (M-1)N mod M) mod 100000007.

Small Case: M=200000 ,N=300000
Large case: M=4000000000000 ,N=6000000000

Solution:

For given values of M and N, equation:
(0 mod M + N mod M + 2N mod M +...+ (M-1)N mod M)
consists of d copies of M/d numbers
0 + d + 2d + 3d + ...+ (m-d)
where d=GCD(M,N).

Reference: R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics 1990, Page 129

Code:

#include <stdio.h>
#define mod 100000007

long long GCD(long long a, long long b)
{
  if(a%b==0)
    return b;
  return GCD(b,a%b);
}

int main()
{
  long long m,n,res=0,i;
  scanf("%lld%lld",&m,&n);
  
  long long d = GCD(m,n);
  long long k = m/d;
  for(i=0;i<k;i++)
    res = (res + ((i*d)%mod))%mod;
  printf("%lld\n",(d*res)%mod);
}