11440 - Help Tomisu

[zuluaga]

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

[pradhanp]

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

[mmonish]

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

Code: Select all

2 1
9999 999
10000000 9900000
1000000 900000
5000 1999
10000000 9999999
100 1
10000 1
100000 9999
3 3
9999999 9899999
100000 100
7 1
11 11
11 5
33 20
0 0

My AC output:

Code: Select all

1
99851434
83058271
3985314
86471500
38637795
64325779
6388459
13359237
1
95631054
18032357
5039
8294399
10644479
20979144

[mmonish]

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

[tobby]

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?

[Robert Gerbicz]

Could anyone give some hints?

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

[tobby]

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...

[calicratis19]

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

[roticv]

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.

[calicratis19]

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