OJ Board

How to reduce the space?
Inclusion Exclusion, even precomputing is too slow.
product of primes go as high as ~O(n!).
Thanks.

You only need to report the answer modulo 100000007. So the product of primes being O(n!) does not matter.

Hint : Euler's totient function

I tried to solve this prob but getting WA.
Anyone check my output for the following input
Input: My AC output:

Got AC.....
now the previous outputs r correct.

Could anyone give some hints?

I only know that Answer = N! - 1 - (those with factors <= M), but I find no way to use this fact at all.

Maybe there is some way to compute the desired number directly?

tobby wrote:Could anyone give some hints?

Euler's totient function+precomputation. And don't forget that: M<=N (without it, it would be much harder)

I guess I need a much bigger hint then.......

All numbers having every prime factors > M must be relative prime to M!. But how do we relate M and N? How do we use Euler phi here?

-- EDIT --

Oh I see - all numbers relatively prime to a number k can be written in the form N*k+v, where v<k and v,k are relatively prime.... I think I see the solution now. Thanks!

Wait.... I then have to find a way to compute phi(N!), where N <= 10^7?

Ah, phi(N!) = phi((N-1)!) * something...

cant understand how to use euler phi in this prob. can anyone pls explain...

phi(N!) = number of numbers between 1 and N! which has no common factors with (1...N) ie number of numbers between 1 and N! with prime factors > N.

i got it . i wasnt properly understanding ur explanation first.maybe u should write with some more stops(.) and blank line . but i got it now .many many thx