首页 > ACM题库 > HDU-杭电 > HDU 4379-The More The Better [解题报告]HOJ
2015
05-24

HDU 4379-The More The Better [解题报告]HOJ

The More The Better

问题描述 :

Given an sequence of numbers {X1, X2, … , Xn}, where Xk = (A * k + B) % mod. Your task is to find the maximum sub sequence {Y1, Y2, … , Ym} where every pair of (Yi, Yj) satisfies Yi + Yj <= L (1 ≤ i < j ≤ m), and every Yi <= L (1 ≤ i ≤ m ).
Now given n, L, A, B and mod, your task is to figure out the maximum m described above.

输入:

Multiple test cases, process to the end of input. Every test case has a single line. A line of 5 integers: n, L, A, B and mod. (1 ≤ n ≤ 2*107, 1 ≤ L ≤ 2*109, 1 ≤ A, B, mod ≤ 109)

输出:

Multiple test cases, process to the end of input. Every test case has a single line. A line of 5 integers: n, L, A, B and mod. (1 ≤ n ≤ 2*107, 1 ≤ L ≤ 2*109, 1 ≤ A, B, mod ≤ 109)

样例输入:

1 8 2 3 6
5 8 2 3 6

样例输出:

1
4

//1003
#include <cstdio>
long long n,l,a,b,mod;
int main()
{
    while(scanf("%lld%lld%lld%lld%lld",&n,&l,&a,&b,&mod)==5)
    {
        if(mod<=l/2||((a*n+b)<=l/2)||(a%mod==0||b%mod==0))
        {
            printf("%lld\n",n);
            continue;
        }
        long long mina=l+1,maxa=-1,sum=0;
        for(int i=1;i<=n;i++)
        {
            long long op=(a*i+b)%mod;
            if(op<=l/2)
            {
                sum++;
                if(maxa<op)
                maxa=op;
            }
            else
            {
                if(mina>op)
                {
                    mina=op;
                }
            }
        }
        if(mina+maxa<=l)
        sum++;
        printf("%lld\n",sum);
    }
    return 0;
}