“十分简单复杂的数论题”
首先，对于所有 $\operatorname{lcm}$ 题，我们都选择用 $\gcd$ 来求。
有 $\operatorname{lcm}(a_i,x)=\frac{a_ix}{\gcd(a_i,x)}$ ，所以，把原来需要求的式子变成：
$ans=\frac{x\times\prod_{i=l}^{r}a_i}{\prod_{i=l}^{r}\gcd(a_i,x)}$
分子好求，直接求出前缀积 $Mul[i]$ 然后和 $x$ 相乘即可。
对于分母，因为有 $N\le 2\times 10^5$ ，所以暴力 $\text{biss}$ 。
我们可以从值域开始考虑，对于 $x\le 2\times 10^5$ ，最多有 $\mathcal O(\log x)$ 个质因数。
而对于：
$a_i=\prod p_k^{t_k},x=\prod p_k^{q_k}$
则有：
$\gcd(a_i,x)=\prod p_k^{\min(t_k,q_k)}$
同理就会有：
所以，我们首先将所有的 $a_i$ 的质因子以及其幂因子存储到一个 $\operatorname{Hash}$ 表里，记录为其编号。然后对于每一次查询的 $x$ ，也这样子干，然后每查询到 $x$ 的一个质因子及其幂时，查询有多少个 $a_i$ 也存在这个质因子（或者其幂）。然后统计答案为 $pri[j]^{tot}$ ，$tot$ 表示满足条件的 $a_i$ 的个数，$pri[j]$ 表示当前质因子。
时间复杂度为 $\mathcal O(n\sqrt n\log n)$ ，但跑不满。后来发现这个算法常数似乎有点大，然后做了一些小优化，结果还是 $\text{T}$ 了一个点，可能是因为 $\operatorname{Hash}$ 和 lower_bound ， upper_bound 都用的 $\text{STL}$ ，所以吸氧过了。
AC Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
| #define int long long
const int MAXN=2e5+1;
const int Mod=1e9+7;
int N,Q,Tot;
int val,Mul[MAXN],Pri[MAXN];
std::vector<int>Cnt[MAXN];
bool Is[MAXN];
inline void Init()
{
memset(Is,1,sizeof(Is));
Is[1]=0;Mul[0]=1;
for(int i=2;i<MAXN;++i)
{
if(Is[i]) Pri[++Tot]=i;
for(int j=1;j<=Tot&&i*Pri[j]<MAXN;++j)
{
Is[i*Pri[j]]=0;
if(i%Pri[j]==0) break;
}
}
}
inline int qPow(int a,int b)
{
int res=1;
while(b)
{
if(b&1) res=res*a%Mod;
a=a*a%Mod;b>>=1;
}
return res%Mod;
}
signed main()
{
read(N,Q);
Init();
for(int i=1,cnt,tmp;i<=N;++i)
{
read(val);
Mul[i]=Mul[i-1]*val%Mod;
while(val!=1)
{
for(int j=1;j<=Tot&&Pri[j]<=val/Pri[j];++j)
{
tmp=1;
while(val%Pri[j]==0)
{
tmp*=Pri[j];val/=Pri[j];
Cnt[tmp].push_back(i);
}
}
if(val!=1) Cnt[val].push_back(i),val=1;
}
}
for(int i=1,l,r,x;i<=Q;++i)
{
read(l,r,x);
int res=1,xx=x;
while(x!=1)
{
for(int j=1;j<=Tot&&Pri[j]<=x/Pri[j];++j)
{
int tmp=1,tot=0;
while(x%Pri[j]==0)
{
tmp*=Pri[j];x/=Pri[j];
tot+=std::upper_bound(Cnt[tmp].begin(),Cnt[tmp].end(),r)-std::lower_bound(Cnt[tmp].begin(),Cnt[tmp].end(),l);
}
res=res*qPow(Pri[j],tot)%Mod;
}
if(x!=1)
{
int tot=std::upper_bound(Cnt[x].begin(),Cnt[x].end(),r)-std::lower_bound(Cnt[x].begin(),Cnt[x].end(),l);
res=res*qPow(x,tot)%Mod;x=1;
}
}
write(Mul[r]*qPow(Mul[l-1]*res%Mod,Mod-2)%Mod*qPow(xx,r-l+1)%Mod),puts("");
}
return 0;
}
|