P4240 毒瘤之神的考验
题目背景
( t{Salamander})的家门口是一条长长的公路。
又是一年春天将至，( t{Salamander})发现路边长出了一排毒瘤！
( t{Salamander})想带一些毒瘤回家，但是，这时毒瘤当中钻出来了一个毒瘤之神！
毒瘤之神：你想要带毒瘤走吗？想要带走毒瘤，就必须回答我的问题！如果答不出来的话，你还是乖乖回家吧！
题目描述
毒瘤之神会问(T)次，每次给定(n),(m)，( t{Salamander})需要回答出(sum_{i=1}^nsum_{j=1}^mvarphi(ij) mod 998244353)。
( t{Salamander})这么辣鸡当然不会做啦，于是把问题丢给了你。
输入输出格式
输入格式：
第一行包含一个正整数(T)。
接下来(T)行，每行包含两个正整数，用空格隔开，表示这次询问的(n),(m)。
输出格式：
包含(T)行每行一个整数表示答案。
说明
对于(40\%)的数据，(T=1,n,mleq 10^5)；
对于(50\%)的数据，(Tleq 1000,n,mleq 10^5)；
对于另外(10\%)的数据，(Tleq 10000,n=mleq 10^5)；
对于(100\%)的数据，(Tleq 10^4,n,mleq 10^5)。
辣鸡( t{Dew})又双叒叕做了20年这个题...
经验：
-
[varphi(ij)=frac{varphi(i)varphi(j)gcd(i,j)}{varphi(gcd(i,j))} ]
-
1e5的多组数据，千万别嫌吝啬预处理的复杂度，(logln)什么的随便往上扔
推式子一波得到
发现万恶之源了吗，(varphi)上面的(T)...
先不管那么多，把式子简化一下。
注意(f G)的可用值只有(nln n)个，所以可用简单的拿(vector)存一下，(f f)直接(nsqrt n)做就好了。
式子变成了
多组询问的话，我们可以对询问进行分块。
预处理
注意这个数组同样要使用(vector)存一下不可能使用的值,否则就爆了。
考虑后两维预处理到(U),那么预处理的复杂度可以简单的认为是(O(U^2n))的。
在询问的时候，根据(lfloorfrac{n}{T} floor)或者(lfloorfrac{m}{T} floor)与(U)的大小关系判断一下。
具体的，若(min(lfloorfrac{n}{T} floor,lfloorfrac{m}{T} floor)le U),直接用前缀和(f T)做个差，复杂度最坏是(O(sqrt n))的
否则直接暴力，复杂度是(O(frac{n}{U}))的
总复杂度是(O(T(sqrt n+frac{n}{U})+nln n+nsqrt n+nU^2))的
然后取个(U=T^{frac{1}{3}})大一点差不多最优了
Code:
#include <cstdio>
#include <vector>
#define ll long long
const ll N=1e5;
const ll U=30;
const ll mod=998244353;
ll pri[N+10],ispri[N+10],mu[N+10],phi[N+10],phiinv[N+10],f[N+10],cnt;
std::vector <ll> G[N+10],T[U+1][U+1];
ll quickpow(ll d,ll k)
{
ll f=1;
while(k)
{
if(k&1) f=f*d%mod;
d=d*d%mod;
k>>=1;
}
return f;
}
void init()
{
mu[1]=phi[1]=1;
for(ll i=2;i<=N;i++)
{
if(!ispri[i])
{
pri[++cnt]=i;
mu[i]=-1;
phi[i]=i-1;
}
for(ll j=1;j<=cnt&&i*pri[j]<=N;j++)
{
ispri[i*pri[j]]=1;
if(i%pri[j]==0)
{
phi[i*pri[j]]=phi[i]*pri[j];
break;
}
else
{
mu[i*pri[j]]=-mu[i];
phi[i*pri[j]]=phi[i]*(pri[j]-1);
}
}
}
for(ll i=1;i<=N;i++)
phiinv[i]=quickpow(phi[i],mod-2);
for(ll i=1;i<=N;i++)
{
ll j;
for(j=1;j*j<i;j++)
{
if(i%j==0)
{
(f[i]+=j*phiinv[j]%mod*mu[i/j])%=mod;
(f[i]+=i/j*phiinv[i/j]%mod*mu[j])%=mod;
}
}
if(j*j==i) (f[i]+=j*phiinv[j]%mod*mu[j])%=mod;
}
for(ll i=1;i<=N;i++)
{
G[i].push_back(0);
for(ll j=1;j*i<=N;j++)
G[i].push_back((G[i][j-1]+phi[i*j])%mod);
}
for(ll i=1;i<=U;i++)
{
for(ll j=1;j<=U;j++)
{
T[i][j].push_back(0);
for(ll k=1;k*i<=N;k++)
T[i][j].push_back((T[i][j][k-1]+f[k]*G[k][i]%mod*G[k][j])%mod);
}
}
}
ll min(ll x,ll y){return x<y?x:y;}
ll max(ll x,ll y){return x>y?x:y;}
int main()
{
init();
ll t,n,m;scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld",&n,&m);ll ans=0;
for(ll l=1,r;l<=min(n,m);l=r+1)
{
r=min(n/(n/l),m/(m/l));
if(max(n/l,m/l)<=U) (ans+=T[n/l][m/l][r]-T[n/l][m/l][l-1])%=mod;
else
{
for(ll i=l;i<=r;i++)
(ans+=G[i][n/l]*G[i][m/l]%mod*f[i])%=mod;
}
}
printf("%lld
",(ans+mod)%mod);
}
return 0;
}
2018.11.26