博文
欧拉函数(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] ++;
}
......
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;......
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);
&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 &&am......