D. Lost Arithmetic Progression
题意
$\space\space\space\space\space$ 问题 给定BC等差数列 且C是AB等差数列的公有元素集合 求A的等差数列的所有可能
分析
问题 给定BC等差数列 且C是AB等差数列的公有元素集合 求A的等差数列的所有可能
子问题1 如何快速判断C 的所有元素在B数列中
子问题2 如何表示A数列的可成立范围
子问题3 计算A数列的方案数
字母表示
B b q y
数列 首项 公差 项数
C c r z
数列 首项 公差 项数
solve 1:
1.B的范围比C大 b <= c && b + (y - 1)q >= c + (z - 1)y //首项和末项
2.C的公差是B公差的倍数 r % q == 0
3.C数列的首项在B中 (c - b) % q == 0
solve 2:
分析情况
我们定义C数列左侧延申的第一个数是 c - r 我们记为C0 而右侧延申的第一个是 c + zy 我们记为Cr
首先 我们发现 C0 AB数列只要不断延申一定会抵达 同理 向后延申也是
如果我们的b首项是大于c - r 即不包含C0 那么我们的A数列可以在左侧无线延申 因为他们的交集就是C
同理右侧延申也是一样
solve 3:
首次 我们知道 要是AB的公告元素C都有 那么我们的dC == lcm(da, db)
如果我们的B首项是<= c - r 即B数列包括C0 那么我们的A数列在公差一定的情况下 能够左右延申的范围已经确定了 就是必须大于左侧延申的第一个数 后右侧延申的第一个数
不然 AB将均包含C0以及Cr 与题意矛盾 所以我们知道 能都延申的范围 是[ c - (c - r) ] / da - 1(A的公差) 即r / da - 1
(因为我们延申 dc / da 次后恰好抵达C0 所以我们需要减少1 这是A 的可操作次数) 那么又因为次数可以为0 则左侧的方案数为 r / da 而右侧也是
则在分布乘法的情况下 为 (r / da) * (r / da)
代码
/* 问题 给定BC等差数列 且C是AB等差数列的公有元素集合 求A的等差数列的所有可能
子问题1 如何快速判断C 的所有元素在B数列中
子问题2 如何表示A数列的可成立范围
子问题3 计算A数列的方案数
字母表示
B b q y
数列 首项 公差 项数
C c r z
数列 首项 公差 项数
solve 1:
1.B的范围比C大 b <= c && b + (y - 1)q >= c + (z - 1)y //首项和末项
2.C的公差是B公差的倍数 r % q == 0
3.C数列的首项在B中 (c - b) % q == 0
solve 2:
分析情况
我们定义C数列左侧延申的第一个数是 c - r 我们记为C0 而右侧延申的第一个是 c + zy 我们记为Cr
首先 我们发现 C0 AB数列只要不断延申一定会抵达 同理 向后延申也是
如果我们的b首项是大于c - r 即不包含C0 那么我们的A数列可以在左侧无线延申 因为他们的交集就是C
同理右侧延申也是一样
solve 3:
首次 我们知道 要是AB的公告元素C都有 那么我们的dC == lcm(da, db)
如果我们的B首项是<= c - r 即B数列包括C0 那么我们的A数列在公差一定的情况下 能够左右延申的范围已经确定了 就是必须大于左侧延申的第一个数 后右侧延申的第一个数
不然 AB将均包含C0以及Cr 与题意矛盾 所以我们知道 能都延申的范围 是[ c - (c - r) ] / da - 1(A的公差) 即r / da - 1
(因为我们延申 dc / da 次后恰好抵达C0 所以我们需要减少1 这是A 的可操作次数) 那么又因为次数可以为0 则左侧的方案数为 r / da 而右侧也是
则在分布乘法的情况下 为 (r / da) * (r / da)
*/
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define _ 0
#define int long long
#define endl '\n'
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int lcm(int a, int b)
{
int g = gcd(a, b);
return a * b / g;
}
signed main()
{
int b, c, q, r, y, z;
cin >> b >> q >> y;
cin >> c >> r >> z;
int rb = b + q * (y - 1);
int rc = c + r * (z - 1);
if(c < b || c > rb || rc < b || rc > rb || r % q != 0 || (c - b) % q != 0) cout << 0 << endl;
else if(c - r < b || rc + r > rb) cout << -1 << endl;
else
{
int ans = 0;
for(int p = 1; p <= r / p; p ++)//枚举 r 的因数p的范围
{
cout << p << endl;
if(r % p == 0) //首先得满足 p是r的因数
{
//以下两个操作是为了避免在对因子遍历有重复的情况
// 比如r = 16 而i = 4
//我们对在sqrt(r)内的因子进行枚举
if(lcm(p, q) == r) //只要满足前提1 就这个因子成立
{
int a = ((r / p) * (r / p)) % mod;//左右分别拓展的个数乘积
ans = (ans + a) % mod;
}
cout << ans << endl;
//我们开始枚举 在sqrt(r)外的另一半因子
if(p * p != r && lcm(r / p, q) == r)
{
//此处的拓展个数为 r / (r / p) = p
int a = (p * p) % mod;
ans = (ans + a) % mod;
}
}
cout << ans << endl;
}
cout << ans << endl;
}
}