2012 Multi-University Training Contest 8
The More The Better
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1474 Accepted Submission(s): 368
Problem Description
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.
Input
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)
Output
For each case, output m in one line.
Sample Input
1 8 2 3 6
5 8 2 3 6
Sample Output
1
4
[cpp] view plaincopy
/*題意是 給出A,B,mod n l
問對於k 從1到n 按公式 Xk = (A * k + B) % mod 求出的串中
找出子串Y1, Y2, ... , Ym 且對於串中任意元素小於l 且任意2元素之和小於l
問 找出的串中 最多有多少個元素 即m的值
*/
/*由題意 Yi + Yj <= L 任意2個元素之和小於l 那麼最多只可能有1個元素大於l
那麼 把所有的小於l/2的都入選 那麼這些數肯定是滿足題目要求的
那麼現在還可以加入一個大於l/2的 前提是 入選的中最大的那個 加上這個數小於l
那麼只要入選的當中的最大的加上沒有入選的中的最小的 如果這2者之和小於l 那麼又可以入選一個
*/
/*一開始做的誤區 ： 把串當成了連續的子串 子串本是可以不連續的*/
#include<stdio.h>
int main()
{
__int64 i,n,l,a,b,mod,ban,num,max,min,x;//max是入選的最大值 min是未入選的最小值
while(scanf("%I64d %I64d %I64d %I64d %I64d",&n,&l,&a,&b,&mod)!=EOF)
{
ban=l/2;num=0;max=-1;min=9999999999999;
for(i=1;i<=n;i++)
{
x=((__int64)((__int64)a*i+b)%mod);
if(x<=ban)// 小於等於l/2 則入選
{
num++;
if(max<x) max=x;
}
else
{
if(min>x) min=x;
}
}
if(max+min<=l) num++;
printf("%I64d\n",num);
}
return 0;
}
