首页 > ACM题库 > HDU-杭电 > HDU 3706-Second My Problem First[解题报告]HOJ
2015
02-21

HDU 3706-Second My Problem First[解题报告]HOJ

Second My Problem First

问题描述 :

Give you three integers n, A and B.
Then we define Si = Ai mod B and Ti = Min{ Sk | i-A <= k <= i, k >= 1}
Your task is to calculate the product of Ti (1 <= i <= n) mod B.

输入:

Each line will contain three integers n(1 <= n <= 107),A and B(1 <= A, B <= 231-1).
Process to end of file.

输出:

Each line will contain three integers n(1 <= n <= 107),A and B(1 <= A, B <= 231-1).
Process to end of file.

样例输入:

1 2 3
2 3 4
3 4 5
4 5 6
5 6 7

样例输出:

2
3
4
5
6

http://acm.hdu.edu.cn/showproblem.php?pid=3706

Second My Problem First

Time Limit: 12000/4000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1330    Accepted Submission(s):
503

Problem Description
Give you three integers n, A and B.
Then we define
Si = Ai mod B and Ti = Min{ Sk | i-A
<= k <= i, k >= 1}
Your task is to calculate the product of
Ti (1 <= i <= n) mod B.
 

 

Input
Each line will contain three integers n(1 <= n <=
107),A and B(1 <= A, B <= 231-1).
Process to end
of file.
 

 

Output
For each case, output the answer in a single
line.
 

 

Sample Input
1 2 3
2 3 4
3 4 5
4 5 6
5 6 7
 

 

Sample Output
2
3
4
5
6
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#define len 0x7fffffff
using namespace std;
struct node
{
   __int64 num;
   int p;
};
node q1[1000010];
//int p[1000010];
int main()
{
   __int64  a,b;
   int  n,i,t;
   while(~scanf("%d%I64d%I64d",&n,&a,&b))
   {
       __int64 ti=1;
         __int64  s=1;

       int head=0,r=0;
    for(i=1;i<=n;i++)
       {
           s=(s*a)%b;
            while(head<r&&q1[r].num>=s) r--;
            q1[++r].num=s;
             q1[r].p=i;
        while(q1[head+1].p<i-a)
                  head++;
            ti=(ti*q1[head+1].num)%b;
         
        }
       printf("%I64d\n",ti);
   }
   return 0;
}

 

参考:http://www.cnblogs.com/cancangood/p/4448680.html


  1. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥

  2. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。

  3. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

  4. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.