#1283 : hiho密码

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Ho根据最近在密码学课上学习到的知识，开发出了一款hiho密码，这款密码的秘钥是这样生成的：对于一种有N个字母的语言，选择一个长度为M的单词；将组成这个单词的所有字母按照顺序不重复的写出（即遇到相同字母时跳过）；然后将字母表剩下的没有使用过的字母按照顺序在其后进行排列。

如对于有5个字母的hiho语，选择单词1, 2, 2, 4, 3（此处数字表示字母在字母表中的顺序），则秘钥为1,2,4,3,5。

但是有一天小Ho在计算出了秘钥之后，却发现他弄丢了一开始选择的单词，于是他找到了你，希望你能够帮他找到能够生成这个秘钥的最短的单词。

输入

每个输入文件包含单组测试数据。

每组测试数据的第一行为一个正整数N，意义如前文所述。

每组测试数据的第二行为N个正整数，用来描述一个秘钥，其中第i个正整数Ai表示秘钥的第i个字符在字母表中的顺序。

对于100%的数据，满足N<=1000，1<=Ai<=N。

对于100%的数据，满足对于任意1<=i, j<=N，若i≠j，则Ai≠Aj。

输出

对于每组测试数据，输出能够生成输入给出的秘钥的最短的单词（空串不认为是单词）。由于字母表没有给出，所以对于每个字母，输出其在字母表中的顺序即可（用空格隔开）。

样例输入
5
1 2 4 3 5
样例输出
1 2 4
题目比较简单这个，就是找到到结束为止最长的上升序列，代码如下：

/**
        Author: SpringHack - springhack@live.cn
        Last modified: 2016-03-28 15:31:22
        Filename: main.cpp
        Description: Created by SpringHack using vim automatically.
**/
#include <iostream>

using namespace std;

int f[1010];

int main()
{
    int n;
    cin >> n;
    int p = 1;
    for (int i=0;i<n;++i)
    {
		cin >> f[i];
        if (i && f[i] < f[i - 1])
            p = i;
    }
    for (int i=0;i<p;++i)
    {
        cout << f[i];
        if (i != p - 1)
            cout << " ";
    }
    return 0;
}

题目2 : 机会渺茫

时间限制:5000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi最近在追求一名学数学的女生小Z。小Z其实是想拒绝他的，但是找不到好的说辞，于是提出了这样的要求：对于给定的两个正整数N和M，小Hi随机选取一个N的约数N'，小Z随机选取一个M的约数M'，如果N'和M'相等，她就答应小Hi。

小Z让小Hi去编写这个随机程序，到时候她review过没有问题了就可以抽签了。但是小Hi写着写着，却越来越觉得机会渺茫。那么问题来了，小Hi能够追到小Z的几率是多少呢？

输入

每个输入文件仅包含单组测试数据。

每组测试数据的第一行为两个正整数N和M，意义如前文所述。

对于40%的数据，满足1<=N,M<=106

对于100%的数据，满足1<=N,M<=1012

输出

对于每组测试数据，输出两个互质的正整数A和B（以A分之B表示小Hi能够追到小Z的几率）。

样例输入
3 2
样例输出
4 1

用到了一个定理：约数个数定理，据说处理10^12秒出，估计平时直接TLE了2333，不过被卡住了，因为TMD最后忘了化简这件事，分子分母要互质才行2333:

/**
        Author: SpringHack - springhack@live.cn
        Last modified: 2016-04-02 10:51:20
        Filename: main.cpp
        Description: Created by SpringHack using vim automatically.
**/
#include <iostream>

using namespace std;

long long getFactorNum(long long  n)
{
    long long i = 2, k = 0, m = n, count = 1;
    while(m != 1)
    {
        for(;i<=m;++i)
            if(m % i == 0)
            {
                k = 1;
                while(m % i == 0)
                {
                    k ++;
                    m /= i;
                }
                count *= k;
            }
    }
    return count;
}

long long gcd(long long n, long long m)
{
    long long r;
    while(m){
        r = n % m;
        n = m;
        m = r;
    }
    return n;
}

int main()
{
    long long n,m;
    int a,b;
    cin >> n >> m;
    int ln = getFactorNum(n);
    int lm = getFactorNum(m);
    int lr = getFactorNum(gcd(n,m));
    //化简，化简，一定要化简！
    int d = gcd(ln*lm,lr);
    a = ln*lm/d;
    b = lr/d;
    cout << a << " " << b << endl;
    return 0;
}

其余的没做，就不发了 0.0