数论/暴力 Codeforces Round #305 (Div. 2) C. Mike and Frog

题目传送门

 1 /*
 2     数论/暴力:找出第一次到a1,a2的次数,再找到完整周期p1,p2,然后以2*m为范围
 3                 t1,t2为各自起点开始“赛跑”,谁落后谁加一个周期,等到t1 == t2结束
 4     详细解释:http://blog.csdn.net/u014357885/article/details/46044287
 5 */
 6 #include <cstdio>
 7 #include <algorithm>
 8 #include <cstring>
 9 #include <iostream>
10 using namespace std;
11
12 typedef long long ll;
13
14 const int MAXN = 1e3 + 10;
15 const int INF = 0x3f3f3f3f;
16
17 int main(void)        //Codeforces Round #305 (Div. 2) C. Mike and Frog
18 {
19     int m;
20     ll h1, a1, x1, y1, h2, a2, x2, y2;
21     while (scanf ("%d%I64d%I64d%I64d%I64d%I64d%I64d%I64d%I64d", &m, &h1, &a1, &x1, &y1, &h2, &a2, &x2, &y2) == 9)
22     {
23         ll t1 = -1, t2 = -1, p1 = -1, p2 = -1;
24         for (int i=1; i<=m; ++i)                //get t1, p1
25         {
26             h1 = (h1 * x1 + y1) % m;
27             if (h1 == a1)    {t1 = i; break;}
28         }
29         if (t1 == -1)    {puts ("-1"); continue;}
30         for (int i=1; i<=m; ++i)
31         {
32             h1 = (h1 * x1 + y1) % m;
33             if (h1 == a1)    {p1 = i; break;}
34         }
35
36         for (int i=1; i<=m; ++i)                //get t2, p2
37         {
38             h2 = (h2 * x2 + y2) % m;
39             if (h2 == a2)    {t2 = i; break;}
40         }
41         if (t2 == -1)    {puts ("-1"); continue;}
42         for (int i=1; i<=m; ++i)
43         {
44             h2 = (h2 * x2 + y2) % m;
45             if (h2 == a2)    {p2 = i; break;}
46         }
47
48         bool ok = false;                        //get t1 == t2
49         for (int i=1; i<=2*m; ++i)
50         {
51             if (t1 == t2)    {ok = true; printf ("%I64d\n", t1);    break;}
52             if (t1 < t2)    t1 += p1;
53             else    t2 += p2;
54         }
55         if (!ok)    puts ("-1");
56     }
57
58     return 0;
59 }
60
61 /*
62 5
63 4 2
64 1 1
65 0 1
66 2 3
67 1023
68 1 2
69 1 0
70 1 2
71 1 1
72 */
时间: 05-25

数论/暴力 Codeforces Round #305 (Div. 2) C. Mike and Frog的相关文章

暴力 Codeforces Round #305 (Div. 2) B. Mike and Fun

题目传送门 1 /* 2 暴力:每次更新该行的num[],然后暴力找出最优解就可以了:) 3 */ 4 #include <cstdio> 5 #include <cstring> 6 #include <iostream> 7 #include <algorithm> 8 #include <string> 9 using namespace std; 10 11 const int MAXN = 5e2 + 10; 12 const int

Codeforces Round #305 (Div. 2) C. Mike and Frog +B. Mike and Fun

Mike has a frog and a flower. His frog is named Xaniar and his flower is named Abol. Initially(at time 0), height of Xaniar is h1 and height of Abol is h2. Each second, Mike waters Abol and Xaniar. So, if height of Xaniar is h1 and height of Abol is 

set+线段树 Codeforces Round #305 (Div. 2) D. Mike and Feet

题目传送门 1 /* 2 题意:对于长度为x的子序列,每个序列存放为最小值,输出长度为x的子序列的最大值 3 set+线段树:线段树每个结点存放长度为rt的最大值,更新:先升序排序,逐个添加到set中 4 查找左右相邻的位置,更新长度为r - l - 1的最大值,感觉线段树结构体封装不错! 5 详细解释:http://blog.csdn.net/u010660276/article/details/46045777 6 其实还有其他解法,先掌握这种:) 7 */ 8 #include <cstd

字符串处理 Codeforces Round #305 (Div. 2) A. Mike and Fax

题目传送门 1 /* 2 字符串处理:回文串是串联的,一个一个判断 3 */ 4 #include <cstdio> 5 #include <cstring> 6 #include <iostream> 7 #include <algorithm> 8 #include <string> 9 using namespace std; 10 11 const int MAXN = 1e3 + 10; 12 const int INF = 0x3f3

Codeforces Round #305 (Div. 1) B. Mike and Feet

Mike is the president of country What-The-Fatherland. There are n bears living in this country besides Mike. All of them are standing in a line and they are numbered from 1 to n from left to right. i-th bear is exactly ai feet high. A group of bears

Codeforces Round #305 (Div. 2) E. Mike and Foam 容斥原理

在一个集合中,找和x互素的数有多少? 用容斥定理,先把每个数质因数分解(每个数至多有6个质因子),奇减偶加,就统计到和x互素的数了. 代码: #include<iostream> #include<vector> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; const int N = 5*100000+10; const int maxn

Codeforces Round #305 (Div. 1) B. Mike and Feet(并查集)

题目链接:点击打开链接 思路:我们把元素从大到小排序, 从大到小依次合并区间, 对于第i个数, 如果他相邻左边的数比他大就合并, 相邻右边也一样.这样, 我们就求出了第i个数为最小值的最大区间. 更新答案即可. 细节参见代码: #include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <string> #include <ve

Codeforces Round #305 (Div. 1)C. Mike and Foam(素数+容斥)

题目链接:点这里!!! 题意: 输入n(n<=2e5),q(q<=2e5).紧接着输入n个数a1~an(ai<=5e5).给定一个空集合. 针对每个q,输入x,如果a[x]在不在集合里面,将a[x]插入进去,并且求当前该集合中有多少对互质的数: 如果a[x]在集合里面,将a[x]删除,并且求当前该集合有多少对互质的数. 题解: 1. 将所有数的素因子求出来.(最多6个) 2.如果将a[x]插入进去,我们检查由a[x]的素因子能组成的数有哪些,全部+1. 比如a[x]=12,我们将2.3.

数学/找规律/暴力 Codeforces Round #306 (Div. 2) C. Divisibility by Eight

题目传送门 1 /* 2 数学/暴力:只要一个数的最后三位能被8整除,那么它就是答案:用到sprintf把数字转移成字符读入 3 */ 4 #include <cstdio> 5 #include <algorithm> 6 #include <cstring> 7 #include <iostream> 8 #include <cmath> 9 #include <vector> 10 using namespace std; 11