CF1866B Battling with Numbers

One_JuRuo · 2023-09-04 09:56:26 · 题解

思路

首先对于 p 和 q，他们都必须是 Y 的倍数，不然 \gcd 就不是 Y 了。

再算出来 \frac X Y 的值，当然如果 X 不是 Y 的倍数，那肯定无解。

因为此题特殊的输入方式，所以我们可以很轻易的得到 \frac X Y 的质因子和个数。

那么对于 \frac X Y 中的一种质因子，要么全给 p，要么全给 q，如果 p 给一些，q 给一些，\gcd 就会比 X 大，所以一个质因子有两种选择，假设 \frac X Y 有 k 个不同的质因子，那么答案就是 2^k。记得答案要取模哦。

AC code

#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
long long n,m,a[100005],b,ans=1;
map<long long,long long>p1,p2;
inline long long qsm(long long a,long long b)
{
    long long ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod,b>>=1;
    }
    return ans;
}
int main()
{
    scanf("%lld",&n);
    for(long long i=1;i<=n;++i) scanf("%lld",&a[i]);
    for(long long i=1;i<=n;++i) scanf("%lld",&b),p1[a[i]]=b;
    scanf("%lld",&m);
    for(long long i=1;i<=m;++i) scanf("%lld",&a[i]);
    for(long long i=1;i<=m;++i) scanf("%lld",&b),p2[a[i]]=b;
    for(auto i:p2)
    {
        if(p1[i.first]<i.second) printf("0"),exit(0);
        if(p1[i.first]-i.second) ans=ans*2%mod;
        p1[i.first]=0;
    }
    for(auto i:p1)
    {
        if(i.second) ans=ans*2%mod;
    }
    printf("%lld",ans);
    return 0;
}