2015
05-24

# 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;
}