小数的分数逼近，题目的思路是挺简单的，假设A=N/D，那么N=[D*A]或者N=[D*A]+1，按照这个公式对D进行枚举，不断更新最佳值即可。下面是我的WA的代码：

#include <stdio.h>
#include <math.h>

int main(int argc, char *argv[])
{
    double A;
    int L;
    int N, D;
    double delta;
    double min;
    
    while (scanf("%lf%d", &A, &L) != EOF)
    {
        min = 10 * L;

        int i;
        
        for (i = 0; i * A <= L && i <= L; ++i)
        {
            int temp_D = i;
            int N1 = (int) i * A;
            double delta1 = fabs(A - (double) N1 / i);

            int N2 = (int) i * A + 1;
            double delta2 = fabs(A - (double)N2 / i);

            if (delta1 < delta2 && delta1 < min)
            {
                D = temp_D;
                N = N1;
                min = delta1;
            }
            else if(delta1 > delta2 && delta2 < min)
            {
                D = temp_D;
                N = N2;
                min = delta2;
            }
        }

        printf("%d %d\n", N, D);
    }
    
    return 0;
}

由于没有测试数据，所以也不知道这道题目究竟错在哪里。我也找来了AC的代码：

#include<stdio.h>
#include<math.h>

int main(void)
{
    double min;
    double A;
    long i;
    long j;
    long N;
    long D;
    long L;
    long pd;
    long pn;

    while (scanf("%lf %ld", &A, &L) != EOF)
    {
        pn = -999999;
        pd = 1;
        min = 9999999;

        for (D=1; D<=L; ++D)
        {
            N = (long)(D * A);
   
            if (N > L)
            {
                break;
            }
   
            for (i=0; i<=1; ++i)
            {
                if (fabs(min - A) > fabs((double)(N+i)/(double)D - A))
                {
                    pn = N+i;
                    pd = D;
                    min = (double)(N+i)/(double)D;
                }
            }
        }
  
        if (pn == -999999)
        {
            for (D=1; D<=L; ++D)
            {
                for (N=1; N<=L; ++N)
                {
                    if (fabs(min - A) > fabs((double)N/(double)D - A))
                    {
                        pn = N;
                        pd = D;
                        min = (double)N/(double)D;
                    }
                }
            }
        }
  
        printf("%ld %ld\n", pn, pd);
    }

    return 0;
}

但是这段AC的代码在输入3.33 9的时候给出的答案是10 3，显然是错误的答案。困惑中。求高人指点。

在实验室睡了一宿。昨儿一激动改了/etc/make.conf：

ACCEPT_KEYWORDS="~x86"

主要是想体验一下传说中的gnome 2.30和gnome shell，探索半天才知道我原来的gentoo用的是stable version，这样一改就改成“以后要用testing version"。

sudo emerge -avuND world

这下好了，乖乖，总共有573个软件包要更新，需要下载1.7G的东西。天知道这1.7G的代码在我的本本上要编译多长时间。不过，量小非君子，无毒不丈夫，索性心一横，就输了yes，让本本自己在那边呼啸去了。

编译到170左右个包时出现了麻烦，libmtp无法编译，我一看是因为其依赖的libpng是1.2版本的，而gentoo testing version的libpng是1.4版本的，这样来来回回搞了许久，终于在google上找到了这篇文章，暂且解决了这个问题。

折腾期间又扫了一眼emerge man page，了解了几个有用的参数如：

• --skip-first
• --keep-going
• --resume

中途还有几个blocked的包，解决方法大概是先uninstall再reinstall，一般就行了；再不行看看USE参数，略微改一下，总之，元发行版，麻烦与灵活共存。

编译的过程emacs死掉了，于是再也无法打开^~~^……就这能干看一些题目。zoj 1372，第一眼一看就是图论的题目。反正也是闲着，临阵磨枪，找来了算法导论，补补图论的基础知识。进一步了解了BFS和DFS，看懂了最小生成树的Prim算法，并参照着别人的代码，采用邻接矩阵的方式，还AC了。真实不容易啊。不过收获也是大大的。

代码： 

#include <iostream>
#include <string>
using namespace std;

const long max_points = 100;
const long infinity = 1000001;

int p, r, length, g[max_points][max_points];
bool flag;

class vertex
{
public:
    int distance;
    bool visited;
};

vertex v[max_points];

void initial()
{
    for(int i = 1; i <= p; i++)
        for(int j = 1; j <= p; j++)
            g[i][j] = infinity;
}

void prim(int origin)
{
    int temp_min;
    int temp_v = 0;
    int sum = 0;

    for(int i = 1; i <= p; i++)
    {
        v[i].distance = g[i][origin];
        v[i].visited = false;
    }

    v[origin].distance = 0;
    v[origin].visited = true;

    sum++;

    while (sum < p)
    {
        temp_min = infinity;
        for(int i = 1; i <= p; i++)
            if(v[i].visited == false && v[i].distance < temp_min)
            {
                temp_min = v[i].distance;
                temp_v = i;
            }
        
        if(temp_min < infinity)
        {
            length += v[temp_v].distance;
            v[temp_v].visited = true;
            sum++;
        }
        else
        {
            flag = true;
            break;
        }

        for(int i = 1; i <= p; i++)
        {
            if(v[i].visited == false && v[i].distance > g[i][temp_v])
            {
                v[i].distance = g[i][temp_v];
            }
        }
    }
}

int main(int argc, char *argv[])
{
    int a, b, c;

    while(cin >> p)
    {
        if(p == 0)
            break;
        cin >> r;

        initial();

        for(int i = 0; i < r; i++)
        {
            cin >> a >> b >> c;
            if(c < g[a][b])
                g[a][b] = g[b][a] = c;
        }
        length = 0;
        prim(1);

        cout << length << endl;
    }

    return 0;
} 

两道题目表面上看起来很相似，解法是不一样的。

1314的本质是给定数[tex]x, y[/tex]，问[tex]ax (\bmod y), a = 1, 2, \cdots [/tex]的周期是多少。依稀记得同余理论和不定方程的某些结论，我猜测周期应该是[tex]\frac{y}{gcd(x, y)}[/tex]，自己验证了下也是对的。具体证明涉及到同余和不定方程，高中的基础全忘了，叹。

程序ac一波三折，先是TLE，后来发现scanf()后面没有写!= EOF，可是这题也没说啥时算输入结束啊……看来是经验不足了；后来又是Presentation Error，仔细检查发现是四个空格输出成了五个空格……叹……

代码： 

#include <stdio.h>

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
    
int main(int argc, char *argv[])
{
    int step, mod;

    while (scanf("%d%d", &step, &mod) != EOF)
    {
        printf("%10d%10d", step, mod);
        if (gcd(step, mod) == 1)
        {
            printf ("    Good Choice\n");
        }
        else
        {
            printf ("    Bad Choice\n");
        }
        printf ("\n");
    }
    
    return 0;
}

zoj 1278和zoj1314很像，于是我尝试着用zoj1314的方法去解决，我甚至求出了通项公式：

[tex]y_n = (Z^{n-1}L + \frac{Z^{n-1} - 1}{Z - 1}I )\bmod M[/tex]

后来发现不行，因为这个式子的增量不是线性常数，需要另觅他法。很无耻的参考了这篇博客，难得体会到了代码之美，用数组做标记（我不知道是不是该这样说，或者hash table？）的手法，某些时候确实很管用，需要进一步熟悉。

代码贴一下吧……虽然是抄袭的^~~^：

#include <iostream>
#include <cstring>
using namespace std;

int main(int argc, char *argv[])
{
    int z, i, m, last, next;
    bool judge[10000];

    int count;
    int n = 1;

    while (cin >> z >> i >> m >> last)
    {
        if (z == 0 && i == 0 && m == 0 && last == 0)
        {
            break;
        }

        memset(judge, false, sizeof(judge));

        count = 0;
        while (true)
        {
            next = (z * last + i) % m;

            if (judge[next])
            {
                break;
            }

            last = next;
            judge[next] = true;

            count ++;
        }

        cout << "Case " << n++ << ": "  << count << endl;
    }
    
    return 0;
}

加油加油啊。

简单题，不知道为什么开始WA了一下。

题目大意是给定一组n个数，那么共有n(n-1)/2个数对，求出所有的互质数对，就是这样。gcd的写法还是值得背下来的。

代码：

#include <stdio.h>
#include <math.h>

int gcd(int a, int b)
{
    return b ? gcd(b, a%b) : a;
}

int main(int argc, char *argv[])
{
    int num;
    int inta[60];
    int i, j;
    int result;

    while (scanf("%d", &num))
    {
        if (num == 0)
        {
            break;
        }
        
        for (i = 0; i < num; ++i)
        {
            scanf("%d", &inta[i]);
        }

        result = 0;
        
        for (i = 0; i < num; ++i)
        {
            for (j = i + 1; j < num; ++j)
            {
                if (gcd(inta[i], inta[j]) == 1)
                {
                    result++;
                }
            }
        }

        if (result == 0)
        {
            printf ("No estimate for this data set.\n");
        }
        else
        {
            printf ("%.6lf\n", sqrt(3.0*num*(num-1)/result));
        }
        
    }
    
    return 0;
}

时间紧迫，继续水题……太不道德了……

题意很明确，给定一个数列[tex]a_i(i = 0, 2, \cdots, n)[/tex]， 对于[tex]m[/tex]，求有多少个partial sum能被m整除，所谓partial sum是[tex]\sum_{i = j}^{k} a_i, j, k \in 1, \cdots n}[/tex]。

想法也很简单。第一种方法是求出所有的partial sum，然后分别判断是否能被m整除，[tex]O(n^3)[/tex]的复杂度。

第二种想法是设定[tex]\sigma_j = \sum_{i=0}^{j} a_i, j = 0, 1, 2, \cdots, n}, \delta_{ij} = \sigma_j - \sigma_k = \sum_{i = k+1}^{j}a_i[/tex]，判断[tex]\delta_{ij}[/tex]能否被[tex]m[/tex]整除。[tex]O(n^2)[/tex]复杂度。照此想法编程，确是TLE：

#include <stdio.h>

#define max_len 10001

int main(int argc, char *argv[])
{
    int n, m;
    int inta[max_len];
    int sum[max_len+1];
    
    while (scanf("%d%d", &n, &m) != EOF)
    {
        int i, j;

        for (i = 0; i < n; ++i)
        {
            scanf("%d", &inta[i]);
        }

        for (i = 0; i <= n; ++i)
        {
            sum[i] = 0;
            for (j = 0; j < i; ++j)
            {
                sum[i] += inta[j];
            }
        }

        int num = 0;
        for (i = 0; i < n; ++i)
        {
            for (j = i + 1; j <= n; ++j)
            {
                if (((sum[j] - sum[i]) % m) == 0)
                {
                    num++;
                }
            }
        }
        printf ("%d\n",num);
    }
    
    return 0;
}

不得不另寻出路。依稀记得当初算法课上关于最大子段和的问题，其复杂度也是一点点从[tex]O(n^3) -> O(n^2) -> O(n \log(n)) -> O(n)[/tex]，在此百度如下两篇文章，茅塞顿开：

• http://hi.baidu.com/hi_chf/blog/item/50017817903f0e11972b43e9.html
• http://bloodybat.blog.hexun.com/2788438_d.html

 大体思路是继续第二种想法，设[tex]\phi_j = \sigma_j \bmod m[/tex]，如果存在[tex]j_k, k = 1, 2, \cdots, n[/tex]，那么[tex]\phi_{j_k} - \phi_{j_s}[/tex]表示一个符合条件的partial sum，此类partial sum可以利用组合数公式[tex]c(n, 2) = \frac{n(n-1)}{2}[/tex]求出。最后注意考虑0这个特殊数字的情况。程序参照上面两篇博客整理下，代码如下： 

#include <string.h>
#include <stdio.h>

int c_sum[5001];

int main ()
{
    int i, n, m;
    int temp, sum, num;
    
    while (scanf("%d %d", &n, &m) != EOF)
    {
        sum = 0, num = 0;
        memset(c_sum, 0, sizeof(int) * (m + 1));
        for (i = 0; i < n; i++)
        {
            scanf("%d", &temp);
            sum = (sum + temp) % m;
            if (!sum)
                num++;
            c_sum[sum]++;
        }
        for (i = 0; i < m; i++)
            num += c_sum[i] * (c_sum[i] - 1) / 2;
        printf ("%d\n", num);
    }
    return 0;
}

路漫漫其修远兮，加油加油。