博文
欧拉函数(2006-07-29 22:00:00)
摘要：是一个定义在整数集的函数，的值等于序列 中与互素的数的个数．
当为素数时，
当为合数时，
若 则 //为什么？
下面将给出计算的一般公式和的一些性质．
定理：设 ,则
证明：由的定义知，的值等于序列中与 互素的数的个数
的值等于序列中与互素的数的个数．
的值等于从减去中与不互素的数 的个数．
是素数 若 则
即是的倍数
中与不互素的数的个数等于中是 的倍数的数的个数. 即
又 为素数，
......
Zju 2180 City Game(2006-07-28 22:15:00)
摘要：事实上和1985一摸一样。
#include <cstdio>#include <string>
/* state: 0.34s, 404kb */
int n, a, b;int m[1000], r[1000], l[1000];
void pm(){ for(int i = 0; i < b; i ++) { printf("%d ", m[i]); } printf("\n");}
int main(){ //freopen("in.txt", "r", stdin); int i, k, j; scanf("%d", &n); for(i = 0; i < n; i ++) { memset(m, 0, sizeof(m)); scanf("%d %d ", &a, &b); //pm(); int max = 0; //dp(n^2......) for(k = 0; k < a; k ++) { for(j = 0; j < b; j ++) { char tc; scanf("%c ", &tc); if(tc == 'R') m[j] = 0; else m[j] ++; } //pm(); for(j = 0; j < b; j ++) { l[j] = j;&nb......
ZJU 1008 Gnome Tetravex (2006-07-27 00:13:00)
摘要：这注释是我写的么？忘记了.......
/* source: zju 1008 *//* describe: dfs *//* status: 6.83s-_- *//* author: sqc2936 */
#include <stdio.h>
int g=0; //Game index int n=0; //Puzzle size int q=0; //How many different types of squares int square[25][4]; //Source squares int count[25]; //Quantity of a certain type of squares int table[25]; //Solution
int place(int pos) { int i;
if(pos==n*n) return 1;
for(i=0; i<q; i++) { if(count[i]==0) continue;
if(pos%n!=0) &nbs......
ZOJ 1221 Risk(2006-07-27 00:10:00)
摘要：/* source: zju 1221 *//* algo: floyd *//* author: St.Crux */
#include <cstdio>
int m[20][20];
int main(){ //freopen("in.txt", "r", stdin); int i, k, j, n, a, t = 0; while(scanf("%d", &a) != EOF) { for(i = 0; i < 20; i ++) { for(k = 0; k < 20; k ++) { m[i][k] = ((i == k) ? 0 : 100); } } for(k = 0; k < a; k ++) { scanf("%d", &j); m[0][j - 1] = 1; m[j - 1][0] = 1; } for(i = 1; i < 19; i ++) { scanf("%d", &a); for(k = 0; k < a; k ++) { scanf("%d", &j); m[i][j - 1] = 1; m[j - 1][i] = 1; } } &n......
Zju 1985 Largest Rectangle in a Histogra(2006-07-27 00:11:00)
摘要：tle了我几个月.......谢谢cqf大牛的算法。
//State: 0.22s 1512kb
//用l,r两个数组保存当前元素向左向右访问能够达到的最大下标，因此可用dp
//另：此题甚bt，数据量大的惊人，而且有陷阱，必须用scanf。我用cin的时候起码读了10s.........
#include <cstdio>
int a[100000], l[100000], r[100000], n;
int main(){ freopen("in.txt", "r", stdin); while(scanf("%d", &n) && n) { int i; double max = 0.00; for(i = 0; i < n; i ++) { scanf("%d", &a[i]); } for(i = 0; i < n; i ++) { l[i] = i; while(l[i] > 0 && a[i] <= a[l[i] - 1]) { l[i] = l[l[i] - 1]; } } //pl(); for(i = n - 1; i >= 0; i --) { r[i] = i; while(r[i] < n - 1 && a[i] <= a[r[i] + 1]) { r[i] = r[r[i] + 1];&nbs......