A. 喜剧的迷人之处在于
切入点在 \(a\)，考虑 \(a\) 是不是完全平方数，是的话直接找最小能匹配的完全平方数即可，不是的话 \(a\) 一定可以表示成 \(kx^2\)
的形式，倒着找到最大的平方因子除去，只需要在 \(L\)~\(R\) 间找到一个最小的数也等于 \(kx^2\) 即可
点击查看代码
#include<bits/stdc++.h>
#define int long long
const int maxn=1e6+10;
const int inf=0x7f7f7f;
using namespace std;
int t,a,l,r;
signed main()
{
// freopen("ex_comedy4.in","r",stdin);
// freopen("T.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>t;
while(t--)
{
cin>>a>>l>>r;
int x=sqrt(a);
if(x*x==a)
{
double b=sqrt(l),c=sqrt(r);
int d=sqrt(l);
if(floor(c)-ceil(b)>=0.0)
{
cout<<((double)d==b?d*d:((int)b+1)*((int)b+1))<<'\n';
continue;
}
cout<<"-1"<<'\n';
continue;
}
else
{
int z=a;
for(int i=x;i>=2;i--)
{
if(z%(i*i)==0)
{
z/=(i*i);
}
}
a*=z;
double b=sqrt(ceil(1.0*l/z)),c=sqrt(r/z);
int d=sqrt(ceil(1.0*l/z));
if(floor(c)-ceil(b)>=0.0)
{
cout<<((double)d==b?d*d*z:((int)b+1)*((int)b+1)*z)<<'\n';
continue;
}
cout<<"-1"<<'\n';
continue;
}
}
return 0;
}
B. 镜中的野兽
抽象题，且数据很水，\(m=\gcd(S)+\operatorname{lcm}(S)\) 一定是 \(\gcd(S)\) 的倍数，所以考虑枚举 \(d=\gcd\),同时上下界同时约去 \(\gcd(S)\)
使 \(lcm=\frac{m-d}{d},gcd=1\),对 \(lcm\) 分解质因数，考虑状压，计算可得 \(1e9\) 内质因数最多 \(9\) 个，且这 \(n\) 个数最后一定存在，一
些数它们的因子没有某些因数，一些数它们的因子有某些因数的最高次方，所以一共 \(2*\) 因数个数个条件，状压每个条件是否满
足，同时枚举这 \(n\) 个数的满足条件状态，要倒叙状压，避免一个数被算多次。
点击查看代码
#include<bits/stdc++.h>
const int maxn=1e5+10;
const int inf=0x7f7f7f;
using namespace std;
int n,m,mod,phi[maxn],cnt,a[maxn],num,ans;
int f[262144][30];
void pre(int x)
{
int s=sqrt(x),tem=x;
for(int i=2;i<=s&&i<=tem;i++)
{
if(tem%i==0)
{
phi[++cnt]=i;
a[cnt]=0;
while(tem%i==0)tem/=i,a[cnt]++;
}
}
if(tem!=1) phi[++cnt]=tem ,a[cnt]=1;
}
void dp(int s)
{
for(int i=(1<<cnt*2)-1;i>=0;i--)
{
for(int j=n-1;j>=0;j--)
{
f[i|s][j+1]=(f[i|s][j+1]+f[i][j])%mod;
}
}
}
void lsx(int st,int s)
{
if(st==cnt+1)
{
dp(s);
return ;
}
for(int i=0;i<=a[st];i++)
{
if(i==0)lsx(st+1,s|1<<(st-1));
else if(i==a[st])lsx(st+1,s|1<<(st-1+cnt));
else lsx(st+1,s);
}
}
void solve(int x)
{
int temp=(m-x)/x;
if(m-x<=x)return ;
cnt=0;
memset(f,0,sizeof f);
f[0][0]=1;
pre(temp);
lsx(1,0);
ans=(ans+f[(1<<(cnt*2))-1][n])%mod;
}
int main()
{
// freopen("T.in","r",stdin);
// freopen("T.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m>>mod;
for(int i=1;i<=sqrt(m);i++)
{
if(m%i==0)
{
solve(i);
if(i*i!=m)solve(m/i);
}
}
cout<<ans;
return 0;
}
/*
*/