上交OJ-1012. 增长率问题

1012. 增长率问题

---

Description

有一个数列，它是由自然数组成的，并且严格单调上升。最小的数不小于S，最大的不超过T。现在知道这个数列有一个性质：后一个数相对于前一个数的增长率总是百分比下的整数（如5相对于4的增长率是25%，25为整数；而9对7就不行了）。现在问：这个数列最长可以有多长？满足最长要求的数列有多少个？

Input Format

输入仅有一行，包含S和T两个数（ 0<S<T≤200000 ）。

30%的数据，0<S<T≤100 ；

100%的数据，0<S<T≤200000。

Output Format

输出有2行。第一行包含一个数表示长度，第二行包含一个数表示个数。

Sample Input

2 10

Sample Output

5
2

样例解释

2 4 5 6 9以及2 4 5 8 10

分析

这道题使用动态规划分析，其关键在于：
(tmp-i)/i=j/100
展开则有：tmp=i+ij/100，即ij能被100整除。

#include <iostream>

using namespace std;

int main()
{
    long long int max_length[200000], max_num[200000];
    int s,t;
    int i,j;
    int tmp;
    long long int maxl=1,maxn; //注意溢出，和最少一个
    cin>>s>>t;
    maxn=t-s+1; //当为一个的时候，其可以有这么多个，考虑质数情况
    for(i=s; i<=t; i++)
        max_length[i]=max_num[i]=1;
    for(i=s; i<=t; i++) {
        for(j=1; j<=100; j++){
            if((i*j)%100 == 0) {
                tmp=i+(i*j)/100;
                if(tmp<=t) {
                    if(max_length[i]+1 > max_length[tmp]) {
                        max_length[tmp] = max_length[i]+1;
                        max_num[tmp]=max_num[i];
                    }
                    else if(max_length[i]+1==max_length[tmp])
                        max_num[tmp]+=max_num[i];
                    if(max_length[tmp]>maxl) {
                        maxl=max_length[tmp];
                        maxn=max_num[tmp];
                    }
                    else if(max_length[tmp]==maxl) 
                        maxn+=max_num[i];
                }
            }
        }
    }
    cout<<maxl<<endl<<maxn<<endl;
    return 0;
}