Count the number of distinct sequences a1, a2, …, an (1 ≤ ai) consisting of positive integers such that gcd(a1, a2, …, an) = x and . As this number could be large, print the answer modulo 109 + 7.
gcd here means the greatest common divisor.
Input
The only line contains two positive integers x and y (1 ≤ x, y ≤ 109).
Output
Print the number of such sequences modulo 109 + 7.
Examples
inputCopy
3 9
outputCopy
3
inputCopy
5 8
outputCopy
0
Note
There are three suitable sequences in the first test: (3, 3, 3), (3, 6), (6, 3).
There are no suitable sequences in the second test.
第一次接触这种数学题，还是自己数学太菜了。。。
这里用容斥原理就好了，（详细的话看其他的博客吧，有时间再更
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<string>
#include<cstring>
#include<set>
#include<queue>
#include<map>
#include<cmath>
using namespace std;
#define maxn 1000005
#define inf 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long int ull;
#define eps 1e-5
typedef pair<int,int> pii;
const ll mod=1e9+7;
ll qpow(ll a,ll b)
{
ll ans=1;
while(b){
if(b%2)ans=ans*a%mod;
b=b/2;
a=a*a%mod;
}
return ans;
}
ll a[maxn];
ll dp[maxn];
int main()
{
ios::sync_with_stdio(false);
ll n,m;
cin>>n>>m;
int cnt=0;
if(m%n){
cout<<0<<endl;
}
else {
for(ll i=1;i<=sqrt(m);i++){
if(m%i==0){
if(i%n==0)a[++cnt]=i;
if(i*i!=m&&m/i%n==0)a[++cnt]=m/i;
}
}
sort(a+1,a+cnt+1);
for(int i=cnt;i>=1;i--){
dp[i]=qpow(2,m/a[i]-1);
for(int j=i+1;j<=cnt;j++){
if(a[j]%a[i]==0){
dp[i]=((dp[i]-dp[j])%mod+mod)%mod;
}
}
}
cout<<dp[1]<<endl;
}
}