_Faineant's blog

How to calculate module over 10^14?
By _Faineant, history, 12 months ago, In English

Suppose Given a expression = (a*b*c)/(x*y*z) But as the value can be very big you have to output the final value mod 100000000000031 (1 <= a, b, c, x, y, z <= 10^18)

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
12 months ago, # |
  Vote: I like it +168 Vote: I do not like it

→ Reply
»
12 months ago, # |
  Vote: I like it -56 Vote: I do not like it 
int mult(int x,int y){ return ((x%mod)*(y%mod))%mod;}
int expo(int x,int y){
  if (y==0) return 1;
  int a=expo(x,y/2);
  a=mult(a,a);
  if (a%2) a=mult(a,x);
  return a;
}
int divide(int x,int y){ return mult(x,expo(y,mod-2));}
//divide(mult(mult(a,b),c),mult(mult(x,y),z));

Multiplication is simple. Exponentiation using binary exponantion(works in log n time). Find modular inverse of the divisor with exponantion(fermat's little theorem) and multiply with x.

→ Reply
  • »
    »
    12 months ago, # ^ |
    ← Rev. 3   Vote: I like it +4 Vote: I do not like it

    Bruh moment, we can simply observe $$$a,b,c,x,y,z$$$ after modulo might have maximum value $$$mod-1 = 100000000000030$$$, this is around $$$10^{14}$$$. $$$10^{14}$$$ $$$*$$$ $$$10^{14}$$$ in the $$$mult$$$ function just explodes at $$$10^{28}$$$.

    → Reply
»
12 months ago, # |
  Vote: I like it +62 Vote: I do not like it

→ Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it +40 Vote: I do not like it

If you don't have __int128, you can avoid overflow when multiplying long long by something similar to binpow

long long mult(long long a, long long b)
{
    if (!b) return 0;
    long long r = mult(a, b/2);
    if (b&1) return ((r+r) % mod + a) % mod;
    return (r+r)% mod;
}

But it will take $$$O(\log b)$$$

→ Reply
»
12 months ago, # |
  Vote: I like it +24 Vote: I do not like it

Since $$$10^{14} < 2^{57}$$$, you can use the double hack from this blog:

uint64_t prod_double(const uint64_t x, const uint64_t y, const uint64_t m) {
	uint64_t c = (double)x * y / m;
	int64_t ans = int64_t(x * y - c * m) % int64_t(m);
	if (ans < 0)
		ans += m;
	return ans;
}
→ Reply
»
12 months ago, # |
← Rev. 4   Vote: I like it +10 Vote: I do not like it

You can obviously create your own BigNum structure or something but that is too much work.

Instead we can shift our look from $$$\mathbb{Z}_{M}$$$, where $$$M=10^{14}$$$, to $$$\mathbb{Z}_{\sqrt{ M }}[\sqrt{M}]$$$. We will essentially keep two parts of each number. Maintaining elements of $$$\mathbb{Z}_{\sqrt{ M }}[\sqrt{ M }]$$$ is easy since we only keep two coefficients which are less than $$$\sqrt{ M }=10^7$$$.

Specifically, if $$$x\in \mathbb{Z}_{\sqrt{ M }}[\sqrt{ M }]$$$ then there are $$$a,b\in\mathbb{Z}_{\sqrt{ M }}$$$ such that $$$x=a+b\sqrt{ M }$$$, this will represent the literal $$$a+b\sqrt{ M }$$$ number in $$$\mathbb{Z}_{M}$$$. If $$$y\in\mathbb{Z}_{M}$$$ then with division there are $$$q,r$$$ such that $$$y=q\sqrt{ M }+r$$$ with $$$0\leq r<\sqrt{ M }$$$ and $$$0\leq q<\sqrt{ M }$$$ (else we would have $$$y\geq q\sqrt{M}\geq M>y$$$), so this is the representation of $$$y$$$ in $$$\mathbb{Z}_{\sqrt{ M }}[\sqrt{ M }]$$$.

Now we carry out the multiplication in $$$\mathbb{Z}_{\sqrt{ M }}[\sqrt{ M }]$$$ as

$$$(a +b\sqrt{ M })(c+d\sqrt{ M })=ac+bdM+(bc+ad)\sqrt{ M }=ac+(bc+ad)\sqrt{ M }$$$

,which we can do now since the multiplications fit in long long.

Keep in mind that this technique is simple and perhaps nice, but it is not a great solution for multiplying big numbers in general.

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    i have seen this trick once, here's code

    long long mmul(long long a,long long b,const long long& Mod)  {
	long long lf=a*(b>>25LL)%Mod*(1LL<<25)%Mod;
        long long rg=a*(b&((1LL<<25)-1))%Mod;
	return (lf+rg)%Mod;
}

    there's no any annoying float number so it's 100% safe.

    → Reply