• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

P5956-[POI2017]Podzielno【数学】

开发技术 开发技术 2周前 (04-06) 6次浏览

正题

题目链接:https://www.luogu.com.cn/problem/P5956


题目大意

(B)进制下,给出序列(a)(a_i)表示数字(i)有多少个。求一个最大的(X)(B)进制下,由给出的数字组成(不一定要用完),且其是(B-1)的倍数。

(q)次询问(X)的第(k)位是几。

(2leq Bleq 10^6,1leq qleq 10^5,1leq a_ileq 10^6,0leq kleq 10^{18})


解题思路

(x_i)表示第(i)位的话就是

[left(sum_{i=0}x_itimes B^iright)%(B-1)=0Rightarrow sum_{i=0}left(x_itimes B^i%(B-1)right)=0
]

拆开单独的一个来看

[x_itimes B^i%(B-1)=( x_i%(B-1) )times ( B^i%(B-1) )
]

[=x_i%(B-1)times 1
]

所以其实就是各位数字的和为(B-1)的倍数就好了。

然后再回头看题目发现有限制(a_igeq 1)。这样如果用上所有数字的和对(B-1)取模为(t)的话,若(t)不为(0),我们就让(a_t)减去一个(1)就好了。

然后对于询问求一个前缀和然后二分

时间复杂度(O(B+qlog B))


code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=1e6+10;
ll B,q,a[N];
signed main()
{
	scanf("%lld%lld",&B,&q);
	ll t=0;
	for(ll i=0;i<B;i++){
		scanf("%lld",&a[i]);
		(t+=a[i]*i)%=B-1;
	}
	if(t)a[t]--;
	for(ll i=0;i<B;i++)a[i]+=a[i-1];
	while(q--){
		ll x;scanf("%lld",&x);x++;
		if(x>a[B-1])puts("-1");
		else printf("%lldn",lower_bound(a,a+B,x)-a);
	}
	return 0;
}

程序员灯塔
转载请注明原文链接:P5956-[POI2017]Podzielno【数学】
喜欢 (0)