hdu 4379 The More The Better 多校联合赛事第8场

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): 1474Accepted Submission(s): 368

Problem Description

Given an sequence of numbers {X₁, X₂, ... , X_n}, where X_k = (A * k + B) % mod. Your task is to find the maximum sub sequence {Y₁, Y₂, ... , Y_m} where every pair of (Y_i, Y_j) satisfies Y_i + Y_j <= L (1 ≤ i < j ≤ m), and every Y_i <= 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*10⁷, 1 ≤ L ≤ 2*10⁹, 1 ≤ A, B, mod ≤ 10⁹)

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

/*题意是  给出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;

}