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.
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.
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.
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[];
//int p[1000010];
int main()
{
__int64 a,b;
int n,i,t;
while(~scanf("%d%I64d%I64d",&n,&a,&b))
{
__int64 ti=;
__int64 s=; int head=,r=;
for(i=;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+].p<i-a)
head++;
ti=(ti*q1[head+].num)%b; }
printf("%I64d\n",ti);
}
return ;
}