Codeforces Round #785 (Div. 2) D. Lost Arithmetic Progression
题意： 给出 b , c b,c b,c两个等差数列数组，输入的 3 3 3个数据分别是开始位置 s t st st，等差数 d d d和数组长度 l e n len len，数组 c c c是数组 a ∩ b a∩b a∩b部分，让我们通过数组 b b b和 c c c恢复数组 a a a，求在满足 b b b和 c c c前提下 a a a数组能构造的数量，如果无解输出 0 0 0 ，如果无穷多解输出 ? 1 -1 ?1 。
思路： 首先我们得判断什么情况下是无解的什么情况下是无穷多解。
无解情况：
d
c
dc
dc不是
d
b
db
db的倍数，
s
t
c
<
s
t
b
∣
∣
e
n
d
c
>
e
n
d
b
stc<stb||endc>endb
stc<stb∣∣endc>endb，
(
s
t
b
?
s
t
c
)
(stb-stc)
(stb?stc)%
d
b
!
=
0
db!=0
db!=0
无穷多解情况： 如果
c
c
c数组首项的前一项
s
t
c
?
d
c
<
s
t
b
stc-dc<stb
stc?dc<stb那么数组
a
a
a可以无限向左扩展，同理如果
c
c
c数组尾项的后一项
e
n
d
c
+
d
c
>
e
n
d
b
endc+dc>endb
endc+dc>endb那么数组
a
a
a可以无限向右扩展。
计算解的个数： 所有的个数和
a
n
s
ans
ans即为所有
d
a
da
da为
d
c
dc
dc的约数且
l
c
m
(
d
a
,
d
b
)
=
d
c
lcm(da,db)=dc
lcm(da,db)=dc，
a
a
a可以向左右分别扩展
d
c
/
d
a
dc/da
dc/da个，那么每个满足的
d
a
da
da带来的贡献即为
d
c
/
d
a
dc/da
dc/da *
d
c
/
d
a
dc/da
dc/da。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
int lcm(int a,int b){return a*b/gcd(a,b);}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int stb,stc,db,dc,lenb,lenc;
const int mod = 1e9+7;
void cf(){//t=100
cin>>stb>>db>>lenb>>stc>>dc>>lenc;
int endb,endc;
endb=stb+(lenb-1)*db;
endc=stc+(lenc-1)*dc;
if(endc>endb||stb>stc||dc%db!=0||(stc-stb)%db!=0){//1)无法构造
cout<<0<<endl;
return ;
}
if(stc-stb<dc||endb-endc<dc){//2)向左向右扩展无限
cout<<"-1"<<endl;
return ;
}
//sqrt(1e9)
int ans=0;
for(int i=1;i*i<=dc;i++){
if(dc%i==0){
if(lcm(i,db)==dc){
ans=(ans+(dc/i)*(dc/i))%mod;
}
if(dc/i!=i&&lcm(dc/i,db)==dc){
ans=(ans+i*i)%mod;
}
}
}
cout<<ans<<endl;
return ;
}
signed main(){
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
int t=1;
cin>>t;
while(t--){
cf();
}
}
