A simple Blog for wyx I've been down the bottle hoping.
BZOJ 4724: [POI2017]Podzielno 数论 二分
发表于: | 分类: Oi | 评论:0 | 阅读:164

首先你需要一个常识

因为$x=1(\mod x-1)$所以$x^k = 1(\mod x-1)$

回头一看……逗比题……显然各位之和是$B-1$就行了

那么如果不是呢

可以删数字么,由于每个数字出现的次数都是$>1$的所以可以直接删去,显然删去两个比删去一个还要差……

对于询问就直接对前缀和二分一下就好了……

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6+5;
typedef long long LL;   

inline LL read() {
    LL x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int n, q;
LL a[N];

int main() {
    LL sum = 0;
    n = read(), q = read();
    for(int i=0;i<n;++i) a[i] = read(), (sum += (a[i]*i))%=(n-1);
    if(sum) a[sum] --;
    for(int i=1;i<n;++i) a[i] = a[i] + a[i-1];
    LL tmp;
    for(int i=1;i<=q;++i) {
        tmp = read();
        int ans = upper_bound(a,a+n,tmp)-a;
        if(ans == n) puts("-1");
        else printf("%d\n",ans);
    }
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP