D.TheNumberofPairs(EducationalCodeforcesRound106(RatedforDiv.2)题解)xiaodangao

题目链接：D. The Number of Pairs
思路：已知$clcm(a,b) - dgcd(a,b) = x$设$gcd(a,b)=g,a = ig,b=jg$。其中$i,j$互质，由于$lcm(a,b) = \frac{ab}{gcd(a,b)}$则原式可以化成：
$cijg-dg=x$所以$g=\frac{x}{cij-d}$那么分子$cij-d$一定是$x$的因数，然后我们可以通过枚举$x$的因数，来确定所有$ij$的取值，那么现在的问题就是对于一个
数$s$，求$ij=s$个数，其中i与j互质。答案是$2^{s素因数个数}$。我们可以通过预处理，用类似于埃氏筛法的炒作来提前算好所有的数的质因数个数。
$Code:$

#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) (x&(-x))
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;

template<typename T>void read(T&x){
static char c;static int f;
for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
static char q[65];int cnt=0;
if(x<0)pc('-'),x=-x;
q[++cnt]=x%10,x/=10;
while(x)
    q[++cnt]=x%10,x/=10;
while(cnt)pc(q[cnt--]+'0');
}
const int N = 2e7+10;
int prime[N];
int tot = 0;bool st[N];
void _prime(){
    rep(i,2,2e7){
        if(st[i] == false){
            prime[++tot] = i;
            if(i>1e4)continue;
            for(int j=i*i;j<=2e7;j+=i){
                st[j] = true;
            }
        }
    }
}
int cnt[N];
void iniv(){
    //cnt[1] = 1;
    rep(i,1,tot){
        for(int j=prime[i];j<=2e7;j+=prime[i])cnt[j]++;
    }
}
ll pows[100];
int _;
void solve(){
    pows[0] = 1;
    rep(i,1,55)pows[i] = pows[i-1]*2;
    _prime();
    iniv();
    read(_);
    while(_--){
        int c,d,x;
        read(c);read(d);read(x);
        ll ans = 0;
        for(int i=1;i*i<=x;i++){
            if(x%i)continue;int sum = (d+i)/c;
            if((d + i)%c){
                goto stk;
            }//判断i×j是否为整数

             ans += pows[cnt[sum]];
             stk:
             if(i*i==x)continue;
             if((d+x/i)%c)continue;
             sum = (d+x/i)/c;
             ans += pows[cnt[sum]];
        }
        write(ans);pc('\n');
    }
}
signed main(){solve();return 0; }

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章