2015
05-23

# 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

#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;
}