首页 > ACM题库 > HDU-杭电 > HDU 4321-Arcane Numbers 2-位运算-[解题报告]HOJ
2015
05-23

HDU 4321-Arcane Numbers 2-位运算-[解题报告]HOJ

Arcane Numbers 2

问题描述 :

Vance and Shackler like playing games. After playing "arcane numbers", they find a new game “arcane numbers 2”. The game is also pretty simple. Vance first chooses 3 non-negative integers A, B and N, then he writes down B+A, B+A*2…B+A*N under base 2 and sends it to Shackler, after that Vance will ask him how many 1s are there in the sequence. However, the sequence is too long for Shackler and he turns to you for help. Given you A, B and N, please help Shackler to solve the problem.

输入:

The first line contains a single integer T (T <= 20), the number of test cases. Then there are T lines with each case in a line. For each case, there are three integers A, B, N. 1<=A<=10000, 1<=B<=10^16, 1<=N<=10^12.

输出:

The first line contains a single integer T (T <= 20), the number of test cases. Then there are T lines with each case in a line. For each case, there are three integers A, B, N. 1<=A<=10000, 1<=B<=10^16, 1<=N<=10^12.

样例输入:

2
4 7 1
5 8 2

样例输出:

Case #1: 3
Case #2: 5

题目:Arcane Numbers 2

 

题意:给定a和b,n,让你求b+a, b+2*a, …….b+n*a里面有多少1.

 

当统计第K位的时候 可以注意到 第 B+T*A 和 B+(T+2^(K+1))*A 位是相同的

那么 第K位的时候 只需要统计2^(K + 1)  - 1次就可以了

当统计第K位的时候 可以注意到 连续的 (2^K)/A都是连续的0 或者连续的1 所以可以考虑直接连续记录(2^K)/A个结果。

那么 第K位的时候 只需要统计N / ((2^K)/A)次就可以了
那么 第K位的时候 只需要统计 2^K/((2^K)/A) 复杂度 变为O(A)

#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;
typedef long long LL;

void Solve(LL a,LL b,LL n)
{
    LL cnt=0;
    LL max=b+a*n;
    for(LL i=0;i<64;i++)
    {
        LL m=(LL)1<<i;
        LL mm=m;
        if(m>max) break;
        m<<=1;
        LL cur=a+b;
        LL j=0;
        while(j<m&&j<n)
        {
            LL upper=cur+(mm-(cur%mm))-(LL)1;
            LL step=(upper-cur)/a+(LL)1;
            if(j+step>=n) step=n-j;
            if(j+step>=m) step=m-j;
            if(cur&(LL)1<<i)
            {
                cnt+=step*(n/m);
                if(j+step<(n%m)) cnt+=step;
                else if(j<(n%m)) cnt+=(n%m)-j;
            }
            cur+=a*step;
            j+=step;
        }
    }
    cout<<cnt<<endl;
}

int main()
{
    int t,k=1;
    LL a,b,n,i,j;
    cin>>t;
    while(t--)
    {
        cin>>a>>b>>n;
        cout<<"Case #"<<k++<<": ";
        Solve(a,b,n);
    }
    return 0;
}

 

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acdreamers/article/details/9290327