The main observations of this problem is if two number is not coprime, there largest prime factors of their greatest common divisors will not exceed 72.
So, we just check all possible pairs of numbers from a to b. hence there will be atmost 20 primes, upto 72. we can apply a bitmask dp approach to check which numbers will benefits us most.
Problem link
Official Editorial
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/// Bismillahir Rahmanir Rahim
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS ios::sync_with_stdio(false);
///solution
void solution(){
ll primes[20]= {2, 3, 5, 7, 11, 13, 17, 19, 23, 29,31, 37, 41, 43, 47, 53, 59, 61, 67, 71};
vector<ll>dp((1<<20));
ll a,b;
cin>>a>>b;
dp[0]=1;
for(ll i=a;i<=b;i++){
int bit=0;
for(int j=0;j<20;j++){
if(i%primes[j]==0) bit|=(1<<j);
}
for(int j=0;j<(1<<20);j++){
if((j&bit)==0)dp[j|bit] += dp[j];
}
}
ll ans=0;
for(int i=0;i<(1<<20);i++){
ans+=dp[i];
}
cout << ans << endl;
}
signed main()
{
IOS
int t;
t=1;
//cin>>t;
while(t--){
solution();
}
return 0;
}
