题目大意
给你(a_1ldots a_n,l,c)每次给你(x,y)，求有多少个序列满足：长度(leq l)，每个元素是([1,c])，循环右移(a_j(xleq jleq y))次后和原序列相同。
(n,qleq 100000,l,cleq{10}^9,lcm(a_1,ldots a_n)leq{10}^13)
题解
显然只有右移(gcd(a_x,a_{x+1},ldots,a_y))次后和原序列相同才满足条件。
先求出(s=gcd(a_x,a_{x+1},ldots,a_y))
枚举长度(i)，答案(ans)为
[sum_{i=1}^lc^{gcd(i,s)}
]
先进行简单的莫比乌斯反演：
[egin{align}
ans&=sum_{i=1}^lc^{gcd(i,s)}\
&=sum_{d|s}c^dsum_{i=1}^l[gcd(i,s)=d]\
&=sum_{d|s}c^dsum_{i=1}^{frac{l}{d}}[gcd(i,frac{s}{d})=1]\
&=sum_{d|s}c^dsum_{i|frac{s}{d}}mu(i)lfloorfrac{l}{id}
floor\
end{align}
]
根据套路，我们要枚举(j=id)
[egin{align}
ans&=sum_{j|s}lfloorfrac{l}{j}
floorsum_{i|j}mu(i)c^frac{j}{i}\
end{align}
]
记(f(i)=sum_{j|i}mu(j)c^frac{i}{j})，发现(f(i))与(s)无关，所以可以先把所有(f(i))预处理出来，每次直接枚举(s)的因子计算。
注意到这题很有一个性质：所有(a_i)的lcm(leq {10}^{13})，那么(s)一定是lcm的因子。(leq {10}^{13})的数最多有(10752)个因子，可以先把这些因子求出来，做一波(因子个数 ext{因子个数}^2)的DP，询问时查表。
时间复杂度：(因子个数O( ext{因子个数}^2+qlog nlog a))
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<utility>
#include<cmath>
#include<functional>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void sort(int &a,int &b)
{
if(a>b)
swap(a,b);
}
void open(const char *s)
{
#ifndef ONLINE_JUDGE
char str[100];
sprintf(str,"%s.in",s);
freopen(str,"r",stdin);
sprintf(str,"%s.out",s);
freopen(str,"w",stdout);
#endif
}
int rd()
{
int s=0,c;
while((c=getchar())<'0'||c>'9');
do
{
s=s*10+c-'0';
}
while((c=getchar())>='0'&&c<='9');
return s;
}
void put(int x)
{
if(!x)
{
putchar('0');
return;
}
static int c[20];
int t=0;
while(x)
{
c[++t]=x%10;
x/=10;
}
while(t)
putchar(c[t--]+'0');
}
int upmin(int &a,int b)
{
if(b<a)
{
a=b;
return 1;
}
return 0;
}
int upmax(int &a,int b)
{
if(b>a)
{
a=b;
return 1;
}
return 0;
}
ll gcd(ll a,ll b)
{
return b?gcd(b,a%b):a;
}
ll lcm(ll a,ll b)
{
return a/gcd(a,b)*b;
}
const ll p=998244353;
ll fp(ll a,ll b)
{
ll s=1;
for(;b;b>>=1,a=a*a%p)
if(b&1)
s=s*a%p;
return s;
}
ll d[100010];
namespace seg
{
struct node
{
int l,r,ls,rs;
ll s;
};
node a[200010];
int rt;
int cnt;
void build(int &p,int l,int r)
{
p=++cnt;
a[p].l=l;
a[p].r=r;
if(l==r)
{
a[p].s=d[l];
return;
}
int mid=(l+r)>>1;
build(a[p].ls,l,mid);
build(a[p].rs,mid+1,r);
a[p].s=gcd(a[a[p].ls].s,a[a[p].rs].s);
}
ll query(int p,int l,int r)
{
if(l<=a[p].l&&r>=a[p].r)
return a[p].s;
int mid=(a[p].l+a[p].r)>>1;
ll s=0;
if(l<=mid)
s=gcd(s,query(a[p].ls,l,r));
if(r>mid)
s=gcd(s,query(a[p].rs,l,r));
return s;
}
}
struct hashset
{
ll v[20010];
int w[20010];
int t[20010];
int h[100010];
int n;
void insert(ll x,int y)
{
int hs=x%100007;
n++;
v[n]=x;
w[n]=y;
t[n]=h[hs];
h[hs]=n;
}
int query(ll x)
{
int hs=x%100007;
int i;
for(i=h[hs];i;i=t[i])
if(v[i]==x)
return w[i];
return 0;
}
};
hashset h;
struct list
{
int v[20000010];
int t[20000010];
int h[20010];
int n;
void add(int x,int y)
{
n++;
v[n]=y;
t[n]=h[x];
h[x]=n;
}
};
list li;
ll a[20010];
int m=0;
ll miu[20010];
ll f[20010];
ll l,c;
ll e=1;
ll g[20010];
ll gao(int x)
{
ll ans=0;
int i;
for(i=1;i<=x;i++)
if(a[x]%a[i]==0)
ans=(ans+l/a[i]*f[i])%p;
ans=(ans+p)%p;
return ans;
}
ll f1[20010];
ll f2[20010];
ll ans[20010];
int main()
{
open("b");
int i;
int n,q;
scanf("%d%lld%lld%d",&n,&l,&c,&q);
for(i=1;i<=n;i++)
{
scanf("%lld",&d[i]);
e=lcm(e,d[i]);
}
for(i=1;ll(i)*i<=e;i++)
if(e%i==0)
{
a[++m]=i;
if(ll(i)*i!=e)
a[++m]=e/i;
}
int j;
sort(a+1,a+m+1);
for(i=1;i<=m;i++)
{
g[i]=fp(c,a[i]);
h.insert(a[i],i);
}
for(i=1;i<=m;i++)
for(j=1;j<=i;j++)
if(a[i]%a[j]==0)
li.add(i,j);
for(i=1;i<=m;i++)
if(a[i]!=1)
{
if(a[i]<=1000000000ll&&e%(a[i]*a[i])==0)
f1[h.query(a[i]*a[i])]=1;
for(j=li.h[i];j;j=li.t[j])
if(li.v[j]!=1&&li.v[j]!=i)
{
f1[i]|=f1[li.v[j]];
f2[i]=1;
}
}
for(i=1;i<=m;i++)
if(f1[i])
miu[i]=0;
else
{
int s=0;
for(j=li.h[i];j;j=li.t[j])
if(!f2[li.v[j]])
s++;
miu[i]=(s&1?1:-1);
}
for(i=1;i<=m;i++)
{
f[i]=0;
for(j=li.h[i];j;j=li.t[j])
f[i]=(f[i]+g[li.v[j]]*miu[h.query(a[i]/a[li.v[j]])])%p;
}
for(i=1;i<=m;i++)
ans[i]=gao(i);
seg::build(seg::rt,1,n);
for(i=1;i<=q;i++)
{
int x,y;
scanf("%d%d",&x,&y);
ll s=seg::query(seg::rt,x,y);
ll ss=ans[h.query(s)];
printf("%lld
",ss);
}
return 0;
}