题解：AT_arc216_d [ARC216D] GCD of Product of Arithmetic Progression
更好的阅读体验
数论题好难。把官解复读一遍，只是把官解写得比较简略的地方说清楚了一点。
首先我们进行如下约定：
- 记
f(x) = \prod \limits_{i=0}^{n-1} \left(bx + di + c\right) 。 - 记
G = \gcd \limits_{i=0}^n f(i) 。G 即是我们需要求解的答案。 - 记
v_p(n) 表示n 的质因数分解中，质数p 的指数。特别地，若p \nmid n ，v_p(n) = 0 。
开始。
首先，假设
接下来，对于质数
- 当
p \mid b \land p \mid d 时，v_p(G) = 0 。此时由于
b, d 均为p 的倍数，由于c 和\gcd(b, d) 互质，因此c 不是p 的倍数。由此
f(x) 的每一项都不是p 的倍数，因此p \nmid G ，得证。 - 当
p \nmid b \land p \mid d 时，v_p(G) = 0 。
在此情况下，由于等差数列的公差
d 是p 的倍数，因此f(x) 中的每一项都\bmod \space p 同余。因此若f(x) 中任意一项不是p 的倍数，则f(x) 就不是p 的倍数。那么考虑
c 和b + c 两项，若两项均为p 的倍数，则b 就是p 的倍数，与p \nmid b 矛盾。因此
f(0) 和f(1) 中至少存在一项不是p 的倍数，因此p \nmid G ，得证。
- 当
p \nmid b \land p \nmid d 时，v_p(G) = v_p(n!) 。第一部分
对于函数
f(x) ，我们记
- 恒等算子
\operatorname{I} f(x) = f(x) 。- 平移算子
\operatorname{E} f(x) = f(x+1) 。- 差分算子
\operatorname{\Delta} f(x) = f(x+1) - f(x) 。同时对于任意算子
\operatorname{OP} ，我们记\operatorname{OP}^k f(x) = \operatorname{OP} \left(\operatorname{OP}^{k-1} f\right)(x) 。那么由二项式定理，有
\begin{align} \operatorname{\Delta}^n f(x) &= \left(\operatorname{E} - \operatorname{I}\right) ^ n f(x) \nonumber \\ &= \sum_{k=0}^n {n \choose k} \operatorname{E}^k (-\operatorname{I})^{n-k} f(x) \nonumber \\ &= \sum_{k=0}^n {n \choose k} (-1)^{n-k} f(x+k) \end{align} 接下来考虑对于一个
n 次多项式g(x) = \sum\limits_{i=0}^{n} a_i \cdot x^i 施加\operatorname{\Delta}^n 算子会发生的变化。我们先观察只进行一次\operatorname{\Delta} 操作。容易发现，\begin{align} \operatorname{\Delta} g(x) &= g(x+1) - g(x) \nonumber \\ &= \sum_{i=1}^n a_i \left((x+1)^n - x^n\right) \nonumber \\ &= a_n {n \choose 1} x^{n-1} + a_n\sum_{i=2}^n {n \choose i}x^{n-i} + \sum_{i=1}^{n-1} a_i \left((x+1)^n - x^n\right) \nonumber \\ &= n \cdot a_n \cdot x^{n-1} + T \nonumber \end{align} 其中
T 是一个次数\le n-2 的多项式。由此我们发现，进行一次
\operatorname{\Delta} 操作后，多项式的次数减少1 ，多项式的最高次项系数乘上了操作前的多项式次数。因此进行完\operatorname{\Delta}^n 操作后，多项式将只剩余常数项，而此项的值为a_n \cdot n! 。那么我们将这个结论代回
f 函数。显然f 函数的最高次系数为b^n ，因此有\begin{align} \operatorname{\Delta}^n f(x) = b^n \cdot n! \end{align} 联立
(1), (2) 可以得到\sum_{k=0}^n {n \choose k} (-1)^{n-k} f(x+k) = b^n \cdot n! 取
x = 0 则有\sum_{k=0}^n {n \choose k} (-1)^{n-k} f(k) = b^n \cdot n! 由于
G \mid \sum\limits_{k=0}^n {n \choose k} (-1)^{n-k} f(k) ，因此G \mid b^n \cdot n! 。所以v_p(G) \le v_p(b^n \cdot n!) 。又因为p \nmid b ，因此v_p(G) \le v_p(n!) 。第二部分
我们考虑对于
p^k ，求出有多少个i 满足p^k \mid bx + di +c 。那么写成同余方程的形式，可以得到
di \equiv -bx - c\pmod {p^k} 这里由于
p 是质数，p \nmid d ，因此d 在\bmod \space p^k 意义下存在逆元。因此只要满足以下条件的i 都满足p^k \mid bx + di +c 。i \equiv d^{-1} \cdot (-bx - c) \pmod {p^k} 由此，满足条件的
i 的数目至少为\frac{n}{p^k} 。接下来对于
x ，考虑v_p(f(x)) 的值。\begin{align} v_p(f(x)) &= \sum_{i=0}^{n-1} v_p(bx + di + c) \nonumber \\ &= \sum_{k = 1}^{+\infty} \sum_{i=0}^{n-1} [v_p(bx + di + c) \ge k] \nonumber \\ &= \sum_{k = 1}^{+\infty} \sum_{i=0}^{n-1} \left[p^k \mid (bx + di + c)\right] \nonumber \\ &\ge \sum_{k=1}^{+\infty} \left\lfloor \frac{n}{p^k}\right\rfloor \nonumber \end{align} 又因为
\begin{align} v_p(n!) &= \sum_{i=1}^n v_p(i) \nonumber \\ &= \sum_{k=1}^{+\infty} \sum_{i=1}^n\left[p^k \mid i\right] \nonumber \\ &=\sum_{k=1}^{+\infty} \left\lfloor \frac{n}{p^k}\right\rfloor \nonumber \end{align} 因此
v_p(G) = \min_{x=0}^n v_p(f(x)) \ge v_p(n!) 综上，我们可以得到，
v_p(G) = v_p(n!) 。命题得证。
- 当
p \mid b \land p \nmid d ，求解v_p(G) 的过程将在下文呈现。
记
我们对
-
在此情形下，由于 $b$ 始终是 $p^k$ 的倍数，因此 $h(k, x)$ 的取值与 $x$ 无关，始终等于 $di + c(i \isin [0, n-1] \cap \Z)$ 中 $p^k$ 的倍数个数。假设这个数为 $n_x$。 -
记 $m = v_p(b)$。在此情形下，由于 $c$ 与 $p^m$ 互质，因此所有满足 $p^m \mid di + c$ 的 $i$ 构成一个公差为 $p^m$ 的等差数列。 那么记满足上述条件的 $i = p^m \cdot i' + j$。则此时 $d(p^m \cdot i' + j) + c$ 是 $p^m$ 的倍数，即 $dj + c$ 是 $p^m$ 的倍数。因此记 $b' = \frac{b}{p^m}$，$c' = \frac{dj + c}{p^m}$，那么 $$ \begin{align} bx + di + c &= p^m b' \cdot x + p^md \cdot i' + p^m c' \nonumber \\ &= p^m (b'x + di' + c) \nonumber \end{align} $$ 在这个式子里，$b', d$ 均不是 $p$ 的倍数，因此这种情况和上述 $p \nmid b \land p \nmid d$ 的情况完全一致！在此情况下，假设 $i'$ 的取值范围是 $[0, n'-1]$，其中 $n'$ 是满足 $p^m \mid di + c$ 的 $i$ 的个数。那么由 $p \nmid b \land p \nmid d$ 的结论，
综上，
综合上述四种情况，最后，本题的答案就是答案是
这题的数学分析部分到这里就结束了！以下是实现细节。
容易发现，对于大部分的质数
首先考虑对于所有质数
我们再思考对于给定质数
可以在
接下来对于
对于
最后，一开始除掉的
至此这道题就做完了。假设
#include<bits/stdc++.h>
#define endl '\n'
#define N 1000006
#define MOD 998244353
using namespace std;
using i64=long long;
inline void add(int &x,int y) {x+=y,x-=x>=MOD?MOD:0;}
inline void dec(int &x,int y) {x+=MOD-y,x-=x>=MOD?MOD:0;}
int tot,fac[N],vis[N],prime[N],mnp[N];
inline int qpow(int x,int y)
{
int ret=1;
for(;y;y>>=1,x=1ll*x*x%MOD)if(y&1)ret=1ll*ret*x%MOD;
return ret;
}
void sieve()
{
for(int i=2;i<N;i++)
{
if(!vis[i])prime[++tot]=i,mnp[i]=i;
for(int j=1;j<=tot&&i*prime[j]<N;j++)
{
vis[i*prime[j]]=1;
mnp[i*prime[j]]=prime[j];
if(i%prime[j]==0)break;
}
}
}
int v_fac(int p,int n)
{
i64 bas=p; int ret=0;
while(n>=bas)ret+=n/bas,bas*=p;
return ret;
}
vector<int> get(int x)
{
vector<int> ret;
while(x>1)
{
ret.push_back(mnp[x]);
int p=mnp[x];
while(x%p==0)x/=p;
}
return ret;
}
int exgcd(int p,int q,int &x,int &y)
{
if(!q)return x=1,y=0,p;
int d=exgcd(q,p%q,y,x);
return y-=p/q*x,d;
}
int get(int n,int d,int c,int pk) // di + c ≡ 0 (mod p^k), i \isin [0, n-1]
{
int x,y,t=(pk-c%pk)%pk;
int g=exgcd(d,pk,x,y);
if(t%g)return 0;
int sol=(1ll*x*(t/g)%(pk/g)+pk/g)%(pk/g);
if(sol>=n)return 0;
return (n-1-sol)/(pk/g)+1;
}
void solve()
{
int n,b,c,d;
scanf("%d%d%d%d",&n,&b,&c,&d);
int g=__gcd(__gcd(b,c),d);
b/=g,c/=g,d/=g;
int ans=fac[n];
vector<int> pd=get(d),pb=get(b);
for(int p:pd)ans=1ll*ans*qpow(qpow(p,v_fac(p,n)),MOD-2)%MOD;
for(int p:pb)if(d%p)
{
ans=1ll*ans*qpow(qpow(p,v_fac(p,n)),MOD-2)%MOD;
int m=1,sum=0; i64 bas=p;
while(b%bas==0)bas*=p,m++;
m--,bas=p;
for(int i=1;i<=m;i++)add(sum,get(n,d,c,bas)),bas*=p;
add(sum,v_fac(p,get(n,d,c,qpow(p,m))));
ans=1ll*ans*qpow(p,sum)%MOD;
}
ans=1ll*ans*qpow(g,n)%MOD;
printf("%d\n",ans);
}
main()
{
sieve(),fac[0]=1;
for(int i=1;i<N;i++)fac[i]=1ll*i*fac[i-1]%MOD;
int T; scanf("%d",&T);
while(T--)solve();
return 0;
}