题目描述
小 Q 最终还是过了独木桥。 前方的地上散落着 B 朵樱花，此时刮起了风，便引来一场樱花雨。 樱花雨一共持续了 N 秒。每一秒都会有 A 朵樱花飘落。小 Q 细心的记录了每一秒时间 后地上樱花的数目，并将其转换成了二进制。小 Q 想请你统计一下这些二进制数一共有多 少个 1。
输入
第一行一个 T 为数据组数。接下来 T 行，每行有 A、B、N，含义如题目所述。 输出 输出 T 行，每行一个整数为对应的答案。
样例输入
2
7 4 1
5 8 2
样例输出
3
5
样例说明
对于第一组样例，初始有 4 朵樱花， 一秒后，共 11 朵樱花，二进制为 1011，答案为 3 对于第二组样例，初始有 8 朵樱花， 一秒后，共 13 朵樱花，二进制为 1101; 两秒后，共 18 朵樱花，二进制为 10010，答案为 3 + 2 = 5
数据规模与约定
对于 30%的数据， 2<=N<=10^3
对于 60%的数据， 2<=N<=10^6
对于 100%的数据， 2<=N<=10^9 ，1<= T <= 20 ， 1<= A <=10 ^4， 1<= B <=10^16 资源限制 每个测试点空间限制 256MB，时间限制 1s。 一共 10 个测试点，满分 100 分
思路：
依次统计二进制等差数列的每一位上分别共有多少个 1 。 对于这一等差数列 B+A，B+A*2，B+A*3，…，B+A*N，显然第 i 项与第 2^K+i 项在第 K 位上的数字相同。 于是，可以将原数列按位拆成循环节统计。 另外，每一个循环节内连续的几个 0 或几个 1 的长度可以用 O(1)的时间复杂度求出。 这样便以 O(A)的时间复杂度和 O(1)的空间复杂度解决了这道题。
代码：
#include<iostream>
#include<cstdio>
using namespace std;
int T;
int f[1<<18];
long long A,B,N,ans;
long long work(long long x,long long wei)
{
long long res=0;
for(long long i=1;i<=x;++i)
{
if((B+A*i)%wei<(wei>>1))
{
i=min(x,i+((wei>>1)-(B+A*i)%wei-1)/A);
}
else
{
long long tmp=min(x,i+(wei-(B+A*i)%wei-1)/A);
res+=tmp-i+1;i=tmp;
}
}
return res;
}
int main()
{
#ifdef yilnr
#else
freopen("flowers.in","r",stdin);
freopen("flowers.out","w",stdout);
#endif
cin>>T;
while(T--)
{
ans=0;
scanf("%lld%lld%lld",&A,&B,&N);
for(long long i=2;i<=(B+A*N)<<1;i<<=1)
{
if(N/i)ans+=N/i*work(i,i);
ans+=work(N%i,i);
}
printf("%lld\n",ans);
}
fclose(stdin);fclose(stdout);
return 0;
}