时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB
小Ho在一条笔直的街道上散步。街道上铺着长度为L的石板，所以每隔L距离就有一条石板连接的缝隙，如下图所示。
小Ho在散步的时候有奇怪的强迫症，他不希望脚踩在石板的缝隙上。（如果小Ho一只脚的脚尖和脚跟分别处于一条缝隙的两侧，我们就认为他踩在了缝隙上。如果只有脚尖或脚跟接触缝隙，不算做踩在缝隙上）
现在我们已知小Ho两只脚的长度F以及每一步步伐的长度D。如果小Ho可以任意选择起始位置，请你判断小Ho能否保持不踩缝隙散步至无穷远处？
第一行是一个整数T，表示测试数据的组数。
每组测试数据包含3和整数L, F和D，含义如上文所述。
对于30%的数据： L <= 1000
对于60%的数据： L <= 100000
对于100%的数据： L <= 100000000, F <= 100000000, D <= 100000000, T <= 20
对于每组数据输出一行YES或者NO，表示小Ho是否能走到无穷远处。
样例输入 2 60 26 60 30 26 75 样例输出 YES NO
解题思路：
在mod L的情况下每次加D，最终相邻点的距离一定为__gcd(L,D)，然后只需要判断是否大于脚长F即可
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); } int main() { int t, l, f, d; scanf("%d", &t); while(t--) { scanf("%d%d%d", &l, &f, &d); if(f > gcd(l,d)) { puts("NO"); } else puts("YES"); } return 0; }
发布时间: 2015年12月7日 13:53 最后更新: 2015年12月12日 23:11 时间限制: 1000ms 内存限制: 128M
描述从前有一只蛤，no，Frog，它too young too simple, sometimes naïve。
蛤，哦不，Frog，最喜欢做的一件事情就跳石头，嘛，蛤在河的这一岸，另一只蛤在河的另一岸，这只蛤想和另一个蛤见面，- - 见面干什么呢。韬韬说我也不知道，咦？你们要知道这个干嘛呀。
蛤当然可以通过石头跳过河啦，只要跳跳跳就能跳过去啦，但是蛤们觉得这太无聊了，蛤要玩个有趣の游戏。于是他们找到了韬韬，韬韬说你们真是naïve呀，这个简单呀。
泥只要召集一群蛤，然后每个人都跳跳跳，看能不能把每个石子都跳过一遍。
蛤们一想，噫，这个游戏好简单啊，我们每个人的弹跳力都不一样，得都跳跳才知道，但是找到一个能跳1个石子的，就一定能跳完呀。
韬韬心想，看来不搞个难的你们是不会罢休了，把河里的石子摆成一个环形，石子共有N个，分别编号0~N-1，假设你们蛤中的一只开始在0号石头，一次可以跳K步，沿着环可以一直跳啦，但是泥萌会发现有些石头怎么也跳不到，泥萌可以告诉我这些不能跳到的石头的编号的总和嘛？
输入第一行是测试样例数t (1 <= t <= 100) 接下来t行每行包括两个正整数n 和 k。 数据范围1 <= n <= 10^9 , 1 <= k <= 100
输出输出包括t行，每行包括不能跳到的石子编号的总和。
样例输入1 复制 2 9 6 4 3 样例输出1 27 0n=9，k=3
0->3->6->0->3.....
0 1 2 3 4 5 6 7 8
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a%b); } int main() { int t; long long n, k; scanf("%d", &t); while(t--) { scanf("%lld%lld", &n, &k); long long temp = gcd(n, k); if(temp == 1) { printf("0\n"); } else { long long sum = n*(n-1)/2; long long s = n/temp; sum -= s*(s-1)/2*temp; printf("%lld\n", sum); } } return 0; }
