MM的数学作业

问题描述

今天，MM在上数学课，数学课的主题是函数。讲完以后老师留了一个家庭作业，让同学们回家思考。题目如下：

定义一个函数，F(x)表示x转成二进制后，二进制中“1”的个数。比如F(279)=5,因为(279)₁₀=( 100010111)₂，其中有5个“1”。

现在有一个序列，已知X₀ = 0，X_i=F(X_i-1)*A+B。老师的问题是求这个序列第K个是多少。

输入格式

输入3个整数，A，B，K，定义如上所述。

输出格式

输出只有一行，序列的第K个的值。

样例输入

样例输出

数据范围

0≤A,B≤ 1,000,000

30% 数据1≤K≤1,000,000

100% 数据1≤K≤1,000,000,000

题解

打几个表，然后就发现当K足够大的时候答案就形成一条链加一个环，直接模拟的时间就浪费在这个环上。

找出这个环，求出环的大小并记录环的每一个元素，K减去链的长度，对环的大小取模得到的就是答案在环中的位置。

数组范围开多大？

打开电脑上的计算器，使用程序员型，把10⁶转换成二进制，有20位，那么f(x)的值不会超过20，f(x)*A+B的值不超过20*10⁶+10⁶= 21000000

所以数组范围开21000000

 1 #include <cstdio>
 2 int A,B,K,f[21000005],t=1,h,max;  //  f[1]=0
 3 bool vis[21000005]; 
 4 int main()
 5 {
 6     int x=0,i,j,cnt,p;
 7     scanf("%d%d%d",&A,&B,&K);
 8     vis[0]=1;
 9     while (K--)
10     {
11         for (cnt=0;x;x-=(x&(-x))) cnt++;
12         x=cnt*A+B;
13         if (x>max) max=x;
14         if (!vis[x]) vis[x]=1,f[++t]=x;
15         else break;
16     }
17     if (++K)
18     {
19         for (h=1;f[h]!=x;h++);
20         p=K%(t-h+1);
21         if (!p) printf("%d",f[t]);
22         else printf("%d",f[p+h-1]);
23     }
24     else printf("%d",x);
25     return 0;
26 }