#PQJ2441x13923. QOJ 2441_13923
QOJ 2441_13923
小时候,小H是一名热爱学习的小学生。有一天,在数学课上,老师留了一道题让大家思考:一个整数,已知它和整数 𝑎 的最大公约数等于 𝑏 ,和整数 𝑐 的最大公约数等于 𝑑 。请算出这个整数的值。
爱学习的小 H 没花多少时间就发现,可能有很多整数都满足这样的条件,于是就去把疑惑告诉老师。老师很高兴,鼓励小 H 找出不小于整数 𝑙 且不大于整数 𝑟 的所有满足条件的整数有哪些,观察一下有没有什么规律。然而这个问题太困难了,小 H 当时没有解决。
现在,已经读大学的小 H 在翻阅小学日记时重新看到了这个问题,可是依然不会做。请你帮忙解决这个问题。由于满足条件的整数可能有很多,你只需要输出它们的和
输入格式
第一行,一个整数 𝑇 , 表示有几组测试数据。
接下来 𝑇 行, 每行为六个由空格隔开的正整数, 依次是 𝑙 , 𝑟 , 𝑎 , 𝑏 , 𝑐 , 𝑑 。
输出格式
输出 𝑇 行,每行一个整数, 依次是每组数据的答案, 即 𝑙 到 𝑟 之间所有和 𝑎 的最大公约数为 𝑏 并且和 𝑐 的最大公约数为 𝑑 的整数之和。 如果不存在这样的整数,输出 0 即可。
样例数据 样例输入 3 1 20 2 2 12 6 4 6 3 3 4 4 1 1000000000 1 1 3 1 样例输出 24 0 333333333666666667 样例解释
第 1 组数据: 1 到 20 之间满足条件的数只有 6 和 18, 和等于 24。
第 2 组数据: 4 到 6 之间不存在满足条件的数。
子任务
对于 10 % 的数据, 1 ≤ 𝑙 ≤ 𝑟 ≤ 10 6
对于 100 % 的数据, 1 ≤ 𝑙 ≤ 𝑟 ≤ 10 30 , 1 ≤ 𝑎 , 𝑏 , 𝑐 , 𝑑 ≤ 10 14 , 1 ≤ 𝑇 ≤ 4 , 保证 𝑏 是 𝑎 的约数, 𝑑 是 𝑐 的约数