Description
wy 和 wjk 是好朋友。
今天他们在一起聊天，突然聊到了以前一起唱过的《蒲公英的约定》。
“说到蒲公英，我给你讲一个故事吧。”
“嗯？”
“从前有两朵蒲公英，他们约定一起长大，在 N 天内每一天都长出同样多的种子，可是， 他们不想让其他植物知道他们到底要长出多少种子，于是他们中的哥哥想出了一个办法，最 开始，他会告诉弟弟一个数 P，然后在接下来的若干天里每一天哥哥会告诉弟弟两个数：a,c， 然后弟弟在这一天会干如下几件事情：
Step 1：首先把 c 和 lastans 按位异或得到 b，最开始 lastans 是 0
Step 2：如果这天的 b 等于 0，则说明他们已经长出了所有要长出的种子，哥哥与弟弟的交 流结束(输入文件也到此结束)
Step 3：如果这天的 b 不等于 0，弟弟会求出一个最小的非负整数 x 使得 ，[题目保证可以找到这样的 x]
Step 4：lastans 赋值为 x
现在给你哥哥给弟弟的所有数字，你能求出每天弟弟要长出的种子的数量(即每天的 x)吗” “唔。。。”
Input
第一行一个整数 P 接下来若干行(不妨认为有 N+1 行)，每行两个整数 a，c，含义如题目描述所示。
Output
一共 N 行，每行一个整数，第 i 行代表第 i 天弟弟要长出的种子的数量(即第 i 天的 x 的值) [第 N+1 天弟弟会在第二步停止，所以不用求出这一天的 x 输出，只作为输入文件结束的标 志]
Sample Input
17
2 8
8 11
5 5
4 12
Sample Output
3
1
12
样例解释
[以下 N 行，每行两个整数，第一个整数代表第 i 天的 a，第二个整数代表第 i 天的 b]
2 8
8 8
5 4
4 0
Data Constraint
对于 30%的数据 1 ≤ N ≤ 1000 1 ≤ P ≤ 1000
对于 60%的数据 1 ≤ N ≤ 10000 1 ≤ P ≤ 60000
另有 10%的数据 每一天的 a 都相等
对于 100%的数据 1 ≤ N ≤ 100000 1 ≤ P ≤ 100000 且 P 是素数 a,b ≤ P-1
题解
这是一道吼题。
%40
直接暴力寻找x即可。
%60~%100
可以用GSBS（大步小步）
大步小步算法是干嘛用的呢？
也就是解决下面这个式子的：
其中p为素数。
然后a、b、p给定要求最小的正整数x为多少。
——一个显然的东西：
那么x就是在0~p这个范围内的一个整数啦。
直接枚举是的，时间复杂度显然不准许。
那么可以考虑优化——
（以下就是GSBS的基本步骤）
首先，我们设一个变量
然后我们再分别设两个变量x,y
那么x就可以表示为：
那么原式：
变成
那么就把丢进hash里，
再依次枚举i找答案即可。
时间复杂度
似乎可以过。
然而我比赛时打wei了，得分与暴力分一样。/_>
100%
震惊，原来题目这么水。
我们发现，题目保证最后的b是0。
也就是说可以考虑从后面的b给倒退回来。
嘿嘿嘿~~
所以就可以套上一个快速幂过掉。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define F(i, a, b) for (int i = a; i <= b; i ++)
#define G(i, a, b) for (int i = a; i >= b; i --)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define mem(a, b) memset(a, b, sizeof a)
#define mec(a, b) memcpy(a, b, sizeof a)
#define mx(a, b) ((a) = max(a, b))
#define mn(a, b) ((a) = min(a, b))
#define N 400
using namespace std;
int P, a, b, lastans;
struct node {
int x, y;
bool operator < (node s) const { return x < s.x || x == s.x && y < s.y; }
} A[N];
#define get getchar()
inline void Re(int &x) {
char c = get; x = 0; int t = 1;
for (; !isdigit(c); c = get) t = (c == '-' ? - 1 : t);
for (; isdigit(c); x = (x << 3) + (x << 1) + c - '0', c = get); x *= t;
}
inline void Wr(int x) {
if (x < 0) { putchar('-'); x = - x; }
if (x > 9) Wr(x / 10); putchar(x % 10 + '0');
}
int ksm(int x, int y) {
int ans = 1;
for (; y ; y >>= 1, x = (1LL * x * x) % P)
if (y & 1) ans = (1LL * ans * x) % P;
return ans;
}
int main() {
freopen("dandelion.in", "r", stdin);
freopen("dandelion.out", "w", stdout);
Re(P); int p = int(sqrt(P)) + 1;
while (1) {
Re(a), Re(b), b ^= lastans, b %= P;
if (!b) return 0; A[0].x = 1, A[0].y = 0;
F(i, 1, p) A[i] = {(1LL * A[i - 1].x * a) % P, i};
sort(A + 0, A + p); int k = P / p;
F(i, 0, k) {
int v = (1LL * ksm(a, ((- i * p) % (P - 1) + (P - 1)) % (P - 1)) * b) % P;
int l = 0, r = p, ans = 0;
while (l <= r) {
int m = l + r >> 1;
if (A[m].x == v) ans = m;
if (A[m].x >= v) r = m - 1; else l = m + 1;
}
if (A[ans].x == v)
{ lastans = i * p + A[ans].y; break; }
}
Wr(lastans); puts("");
}
}
BSGS的算法
uses math;
var
i,j,k,l,n,m,now:longint;
p,a,b,c,tru,an,lastans,kk:int64;
hash,id,x,y,answer:array[0..100000] of longint;
function qsm(a,b,mo:int64):int64;
var
t,y:int64;
begin
t:=1;
y:=a;
while b<>0 do
begin
if(b and 1)=1 then
t:=(t*y) mod mo;
y:=(y*y) mod mo;
b:=b shr 1;
end;
exit(t);
end;
begin
assign(input,'dandelion.in');reset(input);
assign(output,'dandelion.out');rewrite(output);
readln(p);
while not eof do
begin
inc(n);
readln(x[n],y[n]);
end;
for i:=n downto 1 do
begin
if i=n then
begin
answer[n]:=y[n];
end
else
begin
answer[i]:=(y[i] xor qsm(x[i],answer[i+1],p)) mod p;
end;
end;
for i:=2 to n do
begin
writeln(answer[i]);
end;
end.