数列 (HGOI 2019.2.16 T1)

2019-02-16 16:02:17


其实这道题好像还比较花时间的。

题目大意

数据范围

n<=maxlongint

做法

这个么,首先你要找规律,我是一个一个列的,列个三四项基本就行了,你就可以知道,$y_n=x_{2^n-1}$

然后发现如果用高精度+快速幂根本不可做。。

那么怎么办呐,我们采用科学计数法类似的表示方法。用一个超过十,大于一的小数代表这个数,再用一个cnt存下10的指数。快速幂的时候,平方时,指数*2,然后小数平方,如果平方大于10了,就弄成小于10的,然后cnt++。

乘2的时候就简单了,就把小数部分乘个2,然后大于10的话就,cnt++,balabala~

由于2的所有次方各位没有0的,所以不用考虑-1带来的影响(其实大了这个-1本身不算什么)。由于只用输出位数,小数的精度还是绰绰有余的,不用担心会少一位之类的。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,cnt=0;
double a=2.0;
void pow(int k)
{
    if(k<=1) return;
    pow(k/2);
    a=a*a;cnt*=2;
    while(a>10) a/=10,cnt++;
    if(k%2==1)
    {
        a*=2;
        if(a>10) a/=10,cnt++;
    }
}
int main()
{
    scanf("%d",&n);
    if(n<=31)
    {
        int res=1;
        for(int i=1;i<=n;i++)
            res=res*2;
        printf("%d",res-1);
    }
    else
    {
        pow(n);
        printf("%d",cnt);
    }
    return 0;
}