FCDC - Factorial Modulo


You are given 2 integers a, b. Find the number of i for which i! is divisble by a but not b. if i! is divisible by a and b, then you should not count that i.

Input

One line that contains a and b.

Output

Output the result in one line.

Example

Input:
2 3

Output:
1

Constraints

 1 ≤ a ≤ b ≤ 107

Explanation

2! is the only factorial which is divisible by 2 and not divisible by 3.


hide comments
tanardi gunawan: 2019-02-09 16:40:31

good problem

akjol2049: 2018-11-22 16:29:22

nice problem..enjoyed solving it.Thanks Ruhan!

puneethnaik: 2018-08-20 09:10:30

did it using binary search and highest power of a prime in n!. Enjoyed the problem. Hope it helps someone in need. All the best!!!

eagleshadow: 2018-07-01 17:06:34

AC in 10 min :)

Last edit: 2018-07-01 17:07:43
mag1x_: 2018-05-26 11:46:44

Factorization and brain storming :)

excel_blaze: 2018-05-18 22:43:37

that's a easy one :)
factorization+simple logic

holmesherlock: 2017-10-24 16:53:15

dont think too much,,simple logic will get you through

nadstratosfer: 2017-10-20 06:04:48

Seemed easy but took me good 2 hours to crack. The implementation is not so straightforward either - my code came out quite bloated - but considering half of C submissions are slower than my Python3 one, you can probably bruteforce in a few lines also.

visleck: 2017-08-01 22:43:58

@ruhan habib can u please check where my solution is going wrong. I have checked my solution for all cases given in spojtoolkit and it gives the same ans (submission id-19900630)

Last edit: 2017-08-01 22:46:49
amulyagaur: 2017-07-25 19:00:19

No need to brag about AC in one go ... and 0.00 sec... the test cases are weak..
5 63.. the ans should be 2 ... while many submission give 1 as the answer


Added by:Ruhan Habib
Date:2015-11-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Own Problem