Codeforces Round #450 (Div. 2) D. Unusual Sequences 모비우스 계수 허용치

D. Unusual Sequences time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output 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 input 3 9 output 3 input 5 8 output 0 문제: 하나의 그룹을 구성하려면 한 사람이 1보다 크고 모든 수의 gcd가 1이면 y/x, gcd가 1인 서열을 구성하는 것과 같다. 우선 n에 대해 임의로 하나의 그룹으로 나누어 모두 2^(n-1)종이 있음을 증명할 수 있다. 그리고 이 서열의 gcd가 어떤 수 a의 배수가 2^(n/a-1)종인지 알 수 있다.그리고 모비우스 계수로 용척을 하면 답을 얻을 수 있다.1e9의 데이터에 대해 말하자면 최대 11개의 질인수만 있기 때문에 상압 처리에 필요한 모비우스 계수의 값을 사용해서 답을 얻을 수 있다.

#include
#define ll long long
using namespace std;
vector<int> pe;
vector<int> pr;
bool vis[100005];
const int mod = 1e9+7;
int x,y;
ll qpow(int x,int b){
    ll now = x;
    ll sum =1;
    while(b){
        if(b&1) sum = sum*now%mod;
        now = now*now%mod;
        b >>= 1;
    }
    return sum;
}

void init(){
    vis[1] = true;
    for(int i = 2;i <= 100005;i ++){
        if(vis[i] == false) pe.push_back(i);
        for(int j = 0;j < pe.size()&&i*pe[j] < 100005;j ++){
            vis[i*pe[j]] = true;
            if(i%pe[j] == 0) break;
        }
    }
    int now = x;
    for(int i =0;i < pe.size();i ++){
        if(now%pe[i] == 0){
            pr.push_back(pe[i]);
            while(now%pe[i]==0) now /= pe[i];
        }
    }

    if(now != 1) pr.push_back(now);
    int res = pr.size();
    ll ans = qpow(2,x-1);
    for(int i = 1;i < (1<int tmp = 1,f = 1;
        for(int j = 0;j if(i&(1<1;
        }

        ans = (ans+qpow(2,x/tmp-1)*f+mod)%mod;
    }
    printf("%lld
",ans);
}
int main(){
    scanf("%d %d",&x,&y);
    if(y%x){
        puts("0");
        return 0;
    }
    x = y/x;
    init();
    return 0;
}