NOIP模拟测试39,思维禁锢专场「工业题·玄学题·卡常题」

阅读原文时间：2022年07月06日阅读：2

题解

抱歉,题解没时间写了

代码

#include
using namespace std;
#define ll long long
#define A 6666666
#define mod 998244353
ll jie[A],ni[A],acnt[A],bcnt[A];
ll fheng[A],fshu[A];
ll n,m,a,b;
ll meng(ll x,ll k){
ll ans=1;
for(;k;k>>=1,x=x*x%mod)
if(k&1)
ans=ans*x%mod;
return ans;
}
ll C(ll x,ll y){
return jie[x]*ni[x-y]%mod*ni[y]%mod;
}
int main(){
// freopen("a_sample2.in","r",stdin);
scanf("%lld%lld%lld%lld",&n,&m,&a,&b);
a%=mod,b%=mod;
jie[0]=1;ni[0]=1;
acnt[0]=bcnt[0]=1;
for(ll i=1;i<=n+m;i++) jie[i]=jie[i-1]*i%mod,acnt[i]=acnt[i-1]*a%mod,bcnt[i]=bcnt[i-1]*b%mod; ni[n+m]=meng(jie[n+m],mod-2); for(ll i=n+m-1;i>=1;i--)
ni[i]=ni[i+1]*(i+1)%mod;
for(ll i=1;i<=n;i++) scanf("%lld",&fheng[i]),fheng[i]%=mod; for(ll j=1;j<=m;j++) scanf("%lld",&fshu[j]),fshu[j]%=mod; ll ans=0; for(ll i=n;i>=1;i--){
// printf("acnt=%lld bcnt=%lld ")
// printf("fheng[]=%lld n-i+m=%lld m=%lld i=%lld c=%lld acnt=%lld bcnt=%lld\n",fheng[i],n-i+m,m,i,C(n-i+m,m),acnt[m],bcnt[n-i]);
ans=(ans+fheng[i]*((acnt[m]%mod*bcnt[n-i]%mod)%mod)%mod*C(n-i+m-1,m-1)%mod)%mod;
}
for(ll i=1;i<=m;i++){
// printf("fheng[]=%lld n-i+m=%lld m=%lld i=%lld c=%lld acnt=%lld bcnt=%lld\n",fshu[i],n-i+m,m,i,C(n-i+m,m),acnt[m-i],bcnt[n]);
ans=(ans+fshu[i]*((acnt[m-i]%mod*bcnt[n]%mod)%mod)%mod*C(n-i+m-1,n-1)%mod)%mod;
}
printf("%lld\n",ans);
}

题解

题目中说求$\sum\limits_{i=1}^{i<=n}(-1)^{\sum\limits_{j=1}^{j<=m} d(i*j)}$ $d$表示约数个数

$(-1)^{\sum\limits_{j=1}^{j<=m} d(i*j)}$只和奇偶性有关,如果$d(i*j)$为偶数,那么它是没用,偶+偶=偶,偶+奇=奇

那么只考虑约数个数为奇就可以了,发现约数个数为奇当且仅当为完全平方数

我们把$i$ 拆成 $p*q^2$($p$ 没有平方因子),那 $j$ 必须有 $p*r^2$ 的形式,所以对于每个 $i$,都有 $sqrt(\frac{m}{p})$ 个 $j$ 产生贡献。

可以埃筛(需要卡常)可以线筛

我用的埃筛

代码

#include
using namespace std;
#define ll int
#define A 11111111
long long m,n,ans;
ll a[A];
int main(){
scanf("%lld%lld",&n,&m);
for(ll i=1;i<=n;i++) a[i]=i; ll haha=sqrt(n); for(ll i=haha;i>=2;i--){
ll now=i*i;
for(ll j=now;j<=n;j+=now){
while(a[j]%now==0)
a[j]/=now;
}
}
for(ll i=1;i<=n;i++){
long long now=m/a[i];
now=sqrt(now);
if(now&1) ans--;
else ans++;
}
printf("%lld\n",ans);
}