Codeforces Round #450 (Div. 2) D. Unusual Sequences 数学 - 服务器托管|北京服务器租用|机房托管租用|IDC托管租用|机房机柜带宽租用-价格及费用咨询

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
#include
#include
#include
#include
#include
#include
#include
#include
#include
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 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=1;i--){
            dp[i]=qpow(2,m/a[i]-1);
            for(int j=i+1;j

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net

服务器托管，北京服务器托管，服务器租用，机房机柜带宽租用