P5956 题解

caohan · 2022-11-12 19:32:16 · 题解

推荐

我的博客

题意

求在 b 进制下, 0 至 b-1 分别有 a_i 个，能整除 b-1 的最大值的第 k 位是多少。

前置证明

在 b 进制下，x 要是为 b-1 的倍数，x 的数字和必为 x-1 的倍数。

以十进制为例

设 x 的第 y 位值是 x_y ，n 为 x 的位数 ( 个位是第一位 ）。 可得 x 的数字和为：x_1+x_2+x_3+\cdots+x_n

可知 x 为 9 倍数时，x 数字和也为 9 倍数。

该规律可推广至 b>1 的任何数。

思路

先算出题目给的这些数字的和，再扣除一个它除 b-1 的余数的个数，再用前缀和统计，之后二分答案 查找即可。

代码

粘贴不可取，洛谷同维护。

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
long long n;long long q;
long long a[1000005];
long long p[1000005];//前缀和 
long long sum;
long long erfen(long long k,long long l,long long r)//二分答案 
{
    long long ans=-1;

    while(l<=r)
    {
        long long mid=(l+r)/2;
        if(p[mid]>k)
        {
            ans=mid;r=mid-1;
        }
        else 
        {
            l=mid+1;
        }
    }
    return ans;
}
int main()
{
    cin>>n>>q;
    for(long long i=0;i<n;i++)
    {
        cin>>a[i];
        sum+=a[i]*i;
    }
    if(sum%(n-1)!=0)
    {
        a[sum%(n-1)]--;
    }
    for(long long i=0;i<n;i++)
    {
        p[i]=p[i-1]+a[i];
    }//先删后算 
    while(q--)
    {
        long long k;
        cin>>k;
        cout<<erfen(k,0,n-1)<<endl;
        cout<<"1"; 
    }
    return 0;
}