Let {x
i} be the infinite sequence of integers:
1) x
0 = A;
2) x
i = (alpha * x
i-1^2 + beta * x
i-1 + gamma) mod M, for i >= 1.
Your task is to find x
k if you know A, alpha, beta, gamma, M and k.
一开始想求出递推式，结果求不出来。。。
不过由于式子是mod M(1<=M<=1000)，所以xi不同的值最多只有1000个，不算x0，所以至多计算1000次。
定义一个数组存储Xi,另一个数组帮助判断Xi从哪个值开始循环。
WA on 39: ans[0]应该设为A%m, 由于flag[A%m]设为0，所以如果x1算出来是A%m，程序会认为已经和x0重复，而x0是A而不是A%m会出错。另外可以设为A%m的原因是，X1=f(x0)=f(x0%m)
#include <stdio.h>
#include <string.h>
int main(void) {
int A, a, b, c, m, k;
scanf ("%d%d%d%d%d%d", &A, &a, &b, &c, &m, &k);
int ans[1000] = {A%m};
int flag[1001];
memset(flag, -1, sizeof(int)*1001);
flag[A%m]=0;
int i;
for (i = 1; flag[ans[i]=(a*ans[i-1]*ans[i-1]+b*ans[i-1]+c)%m]<0; ++i) {
flag[ans[i]] = i;
}
if (k==0) {
printf ("%d\n", A);
} else if (k >= flag[ans[i]]) {
printf ("%d\n", ans[(k-flag[ans[i]])%(i-flag[ans[i]])+flag[ans[i]]]);
} else {
printf ("%d\n", ans[k]);
}
return 0;
}
给出一个位数n，求出所有位数为n的数的平方的后9位是987654321的个数。
显然只需要考虑数的最低9位，通过另一个程序计算出8位的个数为0，9位的有9个。
当n>9时，最高位有9种选择，其他的(n-10)位有10种选择，所以答案是72*(10^(n-10))。
#include <stdio.h>
int main(void) {
int n;
scanf ("%d", &n);
if (n <= 8) {
printf ("0\n");
} else if (n == 9) {
printf ("8\n");
} else if (n > 9) {
printf ("72");
int i;
for (i = 11; i <= n; ++i) {
printf ("0");
}
printf ("\n");
}
return 0;
}
一开始以为是线性规划的题目，看了网上的提示说是求模线性方程。用拓展欧几里得算法可以得出原方程的一个解。然后就可以根据这个解判断在所给的区间里有几个解。题目比较纠结的地方是边界问题的判断，花了很多时间。以后要多做题才能更快地考虑好边界问题。
由ax+by+c = 0有ax+by = -c，两边取模b得到
ax+by ≡ -c (mod b) 推出 ax ≡ -c (mod b)
模线性方程有解当且仅当gcd(a,b) | -c，有解的情况下方程对模-c有d个不同的解，d=gcd(a,b)
根据拓展欧几里得算法可以算出x0, y0使得d = a*x0+b*y0
则x = x0*(-c/d), y = y0*(-c/d)为原方程ax+by+c=0的一个解
则方程的所有解为x = x0*(-c/d) + i*(b/d), y = y0*(-c/d) - i*(a/d)
计算所有的i使得解在所给区间内的个数即可。
#include <stdio.h>
typedef struct tagNode {
long long d; long long x; long long y;
} Node;
void swap(long long* a, long long* b) {
long long t = *a;
*a = *b;
*b = t;
}
Node euclid(long long a, long long b) {
Node t;
if (!b) {
t.d = a; t.x = 1; t.y = 0;
return t;
}
t = euclid(b, a % b);
Node t1;
t1.d = t.d; t1.x = t.y; t1.y = t.x-(a/b)*t.y;
return t1;
}
int main(void) {
long long a, b, c;
long long x1, x2, y1, y2;
scanf ("%I64d%I64d%I64d", &a, &b, &c);
c = -c;
scanf ("%I64d%I64d%I64d%I64d", &x1, &x2, &y1, &y2);
long long count = 0;
if (a==0 && b==0) {
if (c==0) {
count = (x2-x1+1)*(y2-y1+1);
}
} else if (a==0) {
if (c%b==0 && c/b>=y1 && c/b<=y2) {
count = x2-x1+1;
}
} else if (b==0) {
if (c%a==0 && c/a>=x1 && c/a<=x2) {
count = y2-y1+1;
}
} else { //如果a,b都不为0,用拓展欧几里得算出一个解
Node t = euclid(a, b);
if (c % t.d == 0) {
t.x *= c/t.d;
t.y *= c/t.d;
long long lx, rx, ly, ry;
lx = (x1<=t.x || (x1-t.x)*t.d%b==0) ? (x1-t.x)*t.d/b : (x1-t.x)*t.d/b+1;
rx = (x2>=t.x || (t.x-x2)*t.d%b==0) ? (x2-t.x)*t.d/b : (x2-t.x)*t.d/b-1;
ly = (y1<=t.y || (y1-t.y)*t.d%a==0) ? (t.y-y1)*t.d/a : (t.y-y1)*t.d/a-1;
ry = (y2>=t.y || (t.y-y2)*t.d%a==0) ? (t.y-y2)*t.d/a : (t.y-y2)*t.d/a+1;
if (lx > rx) {
swap(&lx, &rx);
}
if (ly > ry) {
swap(&ly, &ry);
}
if (lx <= ry && ly <= rx) { //求出两个区间交集的元素个数
long long max = (lx>ly) ? lx : ly;
long long min = (rx<ry) ? rx : ry;
count = min-max+1;
}
}
}
printf ("%I64d\n", count);
return 0;
}
水题，一开始看见AC的人也不算很多，以为有点难度。看完之后也是心惊肉跳，以为有什么陷阱。结果程序写完提交就AC了。。大概是题目稍微有点长愿意看下去的人比较少。。
题目就是给你一个指数m(m = 1, 2, 3)，还有n个数(-3到3之间的整数），然后叫你选若干个数, 使求指定指数幂的和最大。
贴一下代码，熟悉一下cppblog环境。
#include <stdio.h>
#include <math.h>
int main(void) {
int n, m;
scanf ("%d%d", &n, &m);
int map[7];
int i;
for (i = -3; i <= 3; ++i) {
map[i+3] = (int)pow(i, m);
}
int sum = 0, s;
for (i = 0; i < n; ++i) {
scanf ("%d", &s);
if (map[s+3] > 0) {
sum += map[s+3];
}
}
printf ("%d\n", sum);
return 0;
}