题解仅供参考

题外话：我得重新整个实用的大数板子了

A

题解

就是个裸的辗转相除法，没什么坑，int就能过

B

题目大意

就是求一堆数里的素数（这题貌似用最简单的判断素数方法就能过）

优化

可以对前1e7个数用筛法判断存表（不过这题确实没必要）

C

题目大意

求1-n的奇数平方和

题解

法一：用公式解决（注意n(n+1)(n+2)会超长整数范围）

法二：预处理打表（核心代码如下）

long long pow2[100001];
pow2[1]=1;
for(int i=1;i<=100000;i+=2){
    pow2[i]=i*i+pow2[i-2];
}

题外话

打表被老师嘲讽了

D

题解

这题挺坑的，还要在出发点相遇（题目没讲清楚吧）

具体的解法是，假设输入的数是a/b c/d

化简 a/b 和 c/d 得到新的 a,b,c,d，答案为 lcm(a,c)/gcd(b,d)

注意分母为1的情况

E

题解

这题是个纯数学题，看平均分后有多少刀是重复的

即 a+b-gcd(a,b)

F

题目大意

求最大质因数是第几个素数

题解

显然用埃氏筛轻松解决

G

题解

显然 c 是 b 的倍数且满足 gcd(a,c)==b 即可

循环 c 累加 b，找到最小的 c 后直接 break

H

题解

根据题目可知，一共有三种形式的小数需要我们去转换成分数，分别为:

有限小数：形如 0.2,0.33
纯循环小数：形如 0.333333333…
非纯循环小数：形如 0.32477777… ，0.24367676767…

显然，无限不循环小数不可能转换为分数（中学知识），而对于上面两种循环小数，我们不妨分情况来讨论。

1、纯循环小数

0.33333… * 10 = 3.33333…

(10 - 1) * 0.33333… = 3

即 9 * 0.33333… = 3

所以 0.33333… = 3/9 = 1/3

再举一个例子

0.474747… * 100 = 47.474747…

(100 - 1) * 0.474747… = 47

即 99 * 0.474747… = 47

所以 0.474747… = 47/99

由上述两个例子我们可以发现，纯循环小数化成分数过后其分子就为所循环单元化成的数，分母则全由9组成，位数和循环数的位数相同。

2、非纯循环小数

0.4777777… * 10 = 4.7777…

0.477777… * 100 = 47.77777…

(100 - 10) * 0.4777777… = 43

所以 0.4777777… = 43/90

再举一个例子

0.323565656… * 1000 = 323.56565656…

0.323565656… * 100000= 32356.565656…

(10000 - 1000) * 0.32356565656… = 32033

所以 0.32356565656… = 32033/99000

由上述两个例子我们可以发现，非纯循环小数化成分数过后其分子为非循环部分与第一个循环部分组成的数减去非循环部分的数，分母则为9与0组成的数，9的位数和循环部分数的位数相同，0的位数则和非循环部分数的位数相同

PS：对于有限小数，不妨看作是非纯循环小数的一种特例子，即0.3 = 0.30000000

I

题目大意

输出[1,2,…,n]的第i个子序列

自序列的顺序按字典序排序

题解

这题就很有意思了

对 n=1 而言，子序列为

[1]

对 n=2 而言，子序列为

[1],[1,2]

[2],[2,1]

对 n=3 而言，子序列为

[1],[1,2],[1,2,3],[1,3],[1,3,2]

[2],[2,1],[2,1,3],[2,3],[2,3,1]

[3],[3,1],[3,1,2],[3,2],[3,2,1]

……

显然可以发现，长度为 n 的序列的子序列 S(n) 满足这样一个关系式：S(n)=n*(S(n-1)+1)

如果按上面的写的话，将 S(n) 个数分为 n 组，每组有 S(n-1)+1 个

那么第 i 个子序列的开头就很明显了，为 x1=i/(S(n-1)+1)+1

假如 n=3,i=9 ,求出的第9个子序列的第一个数为 x1=2

接下来对第 x1 行处理，去除第一个数，新的序列为

[1],[1,3]

[3],[3,1]

即为序列 [1,3] 的子序列

所求即为第 i%(S(n-1)+1)-1 个子序列

以此类推

代码

#include <bits/stdc++.h>
using namespace std;
long long s[21]={0};
bool t[21]={0};
int main(){
    s[1]=1;
    for(int i=2;i<=20;i++)
        s[i]=i*(s[i-1]+1);
    
    int n;
    long long m;
    while(~scanf("%d %lld",&n,&m)){
        memset(t,false,sizeof(t));
        long long k,num=n;
        while(m>0){
            m--;
            k=m/(s[--num]+1);
            m=m%(s[num]+1);
            int number=0,i;
            for(i=1;i<=n;i++){
                if(!t[i])number++;
                if(number==k+1)break;
            }
            printf("%d",i);
            t[i]=true;
            if(m>0)printf(" ");
        }
        printf("\n");
    }
}

J

题目大意

其实就是最大上升子序列和

题解

DP题一道,dp[i]记录从1-i的最大子序列和，不断维护最大值即可，核心代码如下

int maxx=-1;
for(int i=1;i<=n;i++)
{
    int maxs=-1;
    for(int j=0;j<i;j++)
        if(num[i]>num[j])
            maxs=max(maxs,dp[j]);
    dp[i]=maxs+num[i];
    maxx=max(maxx,dp[i]);
}

K

题解

01背包问题，不过这题反向记录不被录取的最小概率会比较好算

dp[i]记录的是 i 万美元下不被录取的最小概率，核心代码如下

long long i,j;
for(i=0;i<10005;i++)
	dp[i]=1;
for(i=1;i<=m;i++)
	scanf("%lld %lf",&a[i],&b[i]);
for(i=1;i<=m;i++)
	for(j=n;j>=a[i];j--)
		dp[j]=min(dp[j],dp[j-a[i]]*(1-b[i]))

L

题解

数塔（数字三角形）什么的已经很老套了，这里就不讲了（不过递归会超时）

M

题目大意

求 N！的位数

题解

求位数我们其实比较容易想到的是 log10(i)+1

log10(N!) = log10(12L*N) = log10(1) + log10(2) + L + log10(N)

最后对和取整+1即为答案

N

题目大意

就是个大数加法板子。。。

题解

略（基本上每个板子都能过吧）

O

题目大意

大数累乘求 N!

题解

10000!足足有近36000位，所以考虑了下压位处理

这题卡了空间没卡时间，打表反而会 MLE，每次运算求解就可

核心代码如下：

memset(a,0,sizeof(a));
a[0]=1;
for(int i=1;i<=n;i++){
    int k=0;
    for(int j=0;j<10000;j++){
        a[j]=i*a[j]+k;
        k=a[j]/10000;
        a[j]%=10000;
    }
}

int i;
for(i = 10000; ; i--)
    if(a[i] != 0)
        break;
printf("%d",a[i]);
i--;
for( ; i != -1; i--)
    printf("%04d",a[i]);
printf("\n");

PS:注意 0! =1

P

题目大意

求每组大数和

题解

还是个大数板子题，不过注意这题有个单独的数据 0 比较恶心

Q

题目大意

求 R 的 n 次方根

题解

对整数部分和小数部分分别运算，注意最后输出格式（小数的乘法确实难搞）

R

题目大意

求区间内的菲波那契数的个数

题解

这题我采用的是先打表后查找的方式，菲波那契数的第500项位数就超过100位了

（然后大数比较我写错了，找BUG找了半天）

普通查找即可（不需要二分就可以过）

代码

#include <bits/stdc++.h>
using namespace std;

int fb[1006][504] ={0};
int a1[504],b1[504];

bool min_fb_a1(int m){
    int i,j;
    for(i = 200; ; i--)
        if(fb[m][i] != 0)break;
    for(j = 200; ; j--)
        if(a1[j] != 0)break;
    if(i<j)return true;
    if(i>j)return false;
    for( ; i != -1; i--)
        if(fb[m][i] < a1[i])
            return true;
        else if(fb[m][i] > a1[i])
            return false;
    return false; 
}

bool min_deng_fb_b1(int m){
    int i,j;
    for(i = 200; ; i--)
        if(fb[m][i] != 0)break;
    for(j = 200; ; j--)
        if(b1[j] != 0)break;
    if(i<j)return true;
    if(i>j)return false;
    for( ; i != -1; i--)
        if(fb[m][i] < b1[i])
            return true;
        else if(fb[m][i] > b1[i])
            return false;
    return true;
}

int main()
{
    int i, j, k;
    string a,b;
    fb[1][0] = 1;
    fb[2][0] = 1;
    for(i = 3; i <= 500; i++){
        k = 0;
        for(j = 0; j <= 200; j++){
            fb[i][j] = fb[i-1][j]+fb[i-2][j]+k;
            k = fb[i][j]/10;
            fb[i][j] = fb[i][j]%10;
        }
    }
    while(cin>>a>>b){
        if(a=="0"&&b=="0")break;
        memset(a1,0,sizeof(a1));
        memset(b1,0,sizeof(b1));
        for(i=a.length()-1;i>=0;i--)a1[a.length()-1-i]=int(a[i])-48;
        for(i=b.length()-1;i>=0;i--)b1[b.length()-1-i]=int(b[i])-48;

        int start,end;
        for(start=1;start<=500;start++)
            if(!min_fb_a1(start))break;
        if(start!=1)start--;
        for(end=start;end<=500;end++)
            if(!min_deng_fb_b1(end))break;
        end--;

        printf("%d\n",end-start);
        
    }
}