[原创]SPOJ TBATTLE - Thor vs Frost Giants [数论+二分]

2017-01-10 00:13:01 Tabris_ 阅读数：422

博客爬取于2020-06-14 22:42:21
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54297591

题目链接：http://www.spoj.com/problems/TBATTLE
------------------------------------------------------------------------------------------.
TBATTLE - Thor vs Frost Giants

number-theory #sliding-window-1

Thor is caught up in a fierce battle with Loki’s army. This army consists of frost giants that have magical powers with them. Their strength levels gets multiplied when they are together. Giants are not highly skilled in the arts of combat, but their sheer size and strength make them formidable opponents even for the Asgardian gods. Thor is no exception. They recover very fast from physical injury but their recovery slows down when they are exposed to extreme heat.
Thor’s hammer can generate heat only in multiples of heat quantum N. Frost giants get killed only when their combined strength level is exactly equal to the heat level of the hammer. Thor is interested in killing a continuous stretch of frost enemies with a throw of his hammer with a preference to kill closer enemies first.
Continuous stretch is defined as a set of consecutive elements.
Help Thor to determine the minimum stretch of frost giants that could be killed in a throw. In case of multiple minimal stretches, output the indices of that stretch that has lowest starting index. If there is no such continuous stretch possible then print -1.

Input

The first line will contain N, the number of Frost Giants in Loki’s army and the Heat quantum.
The second line will contain N integers (a_0, a_2…, a_n-1) - the strength of each frost giant.
Minimum stretch of the army should be 1.

1 ≤ N ≤ 100000
1 ≤ a_i ≤ 100000
Output

Output the range of the minimum stretch of frost giants that could be killed in a throw. In case of multiple minimal stretches, output the indices of that stretch that has lowest starting index.
If there is no such continuous stretch possible then print -1.

Example

Input:
3
1 2 9
Output:
2 2

Input:
5
2 3 4 8 9
Output:
-1

Input:
10
2 4 3 5 17 4 7 5 2 15
Output:
7 8

Explanation

Input #1:
Thor can only kill the stretch [2,2] as this is the minimum length range with strength, multiple of 3.

Input #2:
There is no stretch of frost giants that have combined strength as a multiple of 5.

Input #3:
There are many stretches of frost giants that have strength as multiple of 10. But the minimal stretch with the least indices is from [7,8]. Minimum size stretches are [7, 8] and [8, 9]. Out of them we select [7,8].
------------------------------------------------------------------------------------------.
题目大意：就是给你长度为n的序列a0,a1,...an−1a_0,a_1,...a_{n-1}.找一个最短的区见[a,b][a,b]使得(∏i=abai)%n==0(\prod_{i=a}^ba_i)\%n==0 求最小区间，如果多个就输出最左边的，没有输出−1-1.

解题思路:
首先看到这个题我有两个思路,
思路一: 我可以把每个数根据算数基本定理展开,向右扫,就是单调的了,我们可以确定区间的一个值来二分另一个值,这样复杂度为O(nlog2n)O(nlog_2n)
思路二: 我利用线段树维护区间的乘积取模,然后用尺取法的方法来确定区间 ,这样复杂度同样为O(nlog2n)O(nlog_2n),但是我写了一发wa了…

附本题代码
----------------------------------------------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
// 尺取法的WA了........
# include <bits/stdc++.h>

using namespace std;

# define INF        (~(1<<31))
# define INFLL      (~(1ll<<63))
# define pb         push_back
# define mp         make_pair
# define abs(a)     ((a)>0?(a):-(a))
# define lalal      puts("*******");
# define s1(x)      scanf("%d",&x)
# define Rep(a,b,c) for(int a=(b);a<=(c);a++)
# define Per(a,b,c) for(int a=(b);a>=(c);a--)

typedef long long int LL ;
typedef unsigned long long int uLL ;

const int MOD = 1e9+7;
const int N = 100000+8;
const double eps = 1e-6;
const double PI = acos(-1.0);
void fre(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
}
/*************************************************/
LL a[N];
int n;
struct node{
    int l,r;
    LL val;
    int md(){return (l+r)>>1;}
}tree[N<<2];
# define ll  (rt<<1)
# define rr  (rt<<1|1)
# define mid (tree[rt].md())
void pushup(int rt){
    tree[rt].val = tree[ll].val * tree[rr].val % n;
}
void build (int rt,int l,int r){
    tree[rt].l=l,tree[rt].r=r;
    if(l==r){
        tree[rt].val = a[l];
        return ;
    }
    build(ll,l,mid);
    build(rr,mid+1,r);
    pushup(rt);
}
LL query(int rt,int L,int R){
    if(L<=tree[rt].l&&tree[rt].r<=R)
        return tree[rt].val;

    LL ans = 1ll;
    if(L<=mid) ans=ans*query(ll,L,R)%n;
    if(R> mid) ans=ans*query(rr,L,R)%n;
    return ans%n;
}

int main(){

    while(~s1(n)){
        int flag = -1;
        Rep(i,0,n-1) {
            scanf("%lld",&a[i]),a[i]%=n;
            if(0ll==a[i]&&flag == -1) flag = i;
        }
        if(flag!=-1) {
            printf("%d %d\n",flag,flag);
            continue;
        }

        build(1,0,n-1);
        int mi=1010101,weizhi = -1,weizhi2 = -1;
        LL tem = a[0];
        int l,r;
        l=-1,r=0,a[n]=1;
        while(l<r&&r<n){
            while(r<n&&tem%n) tem=tem*a[++r]%n;
            if(r-l+1<mi&&0 == tem%n) mi=r-l+1,weizhi = l-1,weizhi2 = r;
           // printf("%d %d<<---\n",l,r);
            while(l<r&&0 == tem%n) l=l+1,tem=query(1,l,r)%n,weizhi++;
        }

        if(mi != 1010101) {
            printf("%d %d\n",weizhi,weizhi2);
            continue;
        }
        puts("-1");
    }
    return 0;
}