昨天因为要给可儿讲睡前故事，所以没有刷水题，今天继续：

• 1224: 相当水的一道题，就是考冒泡排序的次数，不过题目中相当于是一个循环序列，分析示例可以发现，其实就是相当于把这个循环的序列在中间分成两部分，然后对两部分进行冒泡排序，比如``1 2 3 4，可以分成1 2和3 4，1 2 3 4 5可以分成1 2和3 4 5`，来分别进行排序，再把次数相加即可得到答案。

  代码如下：

    #include <iostream>
    using namespace std;
  
    int main(){
        int amount, n;
        cin >> amount;
        while(amount){
            cin >> n;
            if(n % 2 == 0)
                cout << n / 2 * (n / 2 - 1) << endl;
            else
                cout << n / 2 * (n / 2 - 1) / 2 + n / 2 * (n / 2 + 1) / 2 << endl;
            amount--;
        }
    }
  

• 1247: 我发现ACM很喜欢在质数啊、互质、因数啊这些概念上出题啊。。。
  这道题如果真的一个个去求约数然后求和，结果想都不用想肯定是超时，我感觉没有什么思路，点进Discuss，发现一个大牛给了一个方法，用筛法，直接打表给答案，筛法，感觉很高端的样子啊，立刻Google之，发现原来是一种求质数的方法，在百度百科上找到了解释：

  先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。

  而这题使用筛法，思路就是，建立一个全为0的数组num[n]，然后从1开始遍历数组，对每一个项num[i]，其之后所有角标能被i整除的项，值都加上i。比如遍历到2，就把num[4], num[6], num[8]...的值加2，这样，数组中任意一项，其角标对应的约数和就是这一项的值。然后有输入时，直接查数组输出即可。

  代码如下：

    #include <iostream>
    #include <iomanip>
    using namespace std;
  
    int main(){
        int num[60001], tmp;
        for(int i = 0; i < 60001; i++)
            num[i] = 0;
        for(int i = 1; i <= 60000; i++){
            for(int j = i * 2; j <= 60000; j += i)
                num[j] += i;
        }
        cout << "PERFECTION OUTPUT" << endl;
        while(cin >> tmp){
            if(tmp == 0){
                cout << "END OF OUTPUT" << endl;
                break;
            }else{
                cout << setw(5) << tmp << "  ";
                if(num[tmp] == tmp)
                    cout << "PERFECT" << endl;
                else if(num[tmp] > tmp)
                    cout << "ABUNDANT" << endl;
                else
                    cout << "DEFICIENT" << endl;
            }
        }
    }