跳到主要内容

7-2 国王的奖励——分数取模、分治思想、快速幂、int64的乘法模运算

· 阅读需 8 分钟
El Syzomnia
El Syzomnia
El Furnia 所有者

1 问题​

题面描述

国际象棋是很久以前由一个印度人 Shashi 发明的，当他把该发明献给国王的时候，国王很高兴，就许诺可以给这个发明人任何他想要的奖赏。Shashi 要求以这种方式给他一些粮食：棋盘的第 1 个方格里只放 1 粒麦粒，第 2 格 q 个,第 3 格 q^2^ 个,第 4 格 q^3^ 个……，直到 n 个格子全部放满。这个奖赏最终会是什么样子的呢？Shashi 已经有算法了，请你算一算吧。

当然 Shashi 并不关心具体的数有多少了，他有一个检验你的答案是否与他心意相通的办法:把你求出的答案对 100000007 取模看看和 Shashi 算的是否一样就行了。

输入描述

本题输入具有多组样例。

第一行为一个数 t (1 ≤ t ≤ 500)，代表测试数据的组数。

之后的 t 行，每行两个数 q, n (1 ≤ q, n ≤ 10^18^)，含义见题目描述。

输出描述

输出共 t 行，每行一个数，为你算的答案。 友情提醒：你算的答案应该比 100000007 小。

样例描述

样例输入：

3
2 1
2 2
2 3

样例输出：

1
3
7

样例解释

对于样例：

  • q = 2, n = 1 时仅有1个麦粒
  • q = 2, n = 2 时有 1 + 2 = 3 个麦粒
  • q = 2, n = 3 时有 1 + 2 + 2^2^ = 7 个麦粒

代码长度限制｜16 KB
时间限制｜1000 ms
内存限制｜256 MB

2 分析​

2.1 数学抽象​

该问题本质为等比数列求和问题，11 为首项，qq 为公比，nn 为项数。 需要注意：

  • 每次输入的 qq, nn 可能不同；
  • qq, nn 的范围超过 int32，需要用 int64 来存储；
  • 结果要对 100000007100000007 取模；
  • 计算过程中涉及到大数乘法，直接用 * 运算符会造成数据溢出，需要用自己设计的大数乘法模运算作为替代。

7-3 起泡排序——从冒泡到归并

· 阅读需 2 分钟
El Syzomnia
El Syzomnia
El Furnia 所有者

问题​

题面描述

如下是一个起泡排序的修改程序:

long long BubbleSort(int r[],int n){
int bound,exchange=n-1;
long long ans=0;
while(exchange!=0){
    bound=exchange,exchange=0;
    for(int j=0;j<bound;j++){
        if(r[j]>r[j+1]) 
        {
            int temp=r[j];
            r[j]=r[j+1];
            r[j+1]=temp;
            ans++;
            exchange=j;
        }
    }
}
return ans;
}

请你给出上述函数的返回值。

输入描述

第一行一个正整数 n (1 ≤ n ≤ 2⋅10^5^) 接下来一行共 n 个数，依次为 r[] 中的元素且 r >中的元素 r[i] (0 ≤ i < n) 满足 −10^18^ ≤ r[i] ≤ 10^18^。

输出描述

一行一个数，函数的返回值。

样例

样例1

样例输入

1
1

样例输出

0

样例2

样例输入

2
1 2

样例输出

0

代码长度限制 | 16 KB
时间限制 | 1000 ms
内存限制 | 512 MB

分析​

要求对一个最大有 2⋅1052 \cdot 10^5（约 2182^{18}）个元素的数列进行降序排序，并输出排序过程中发生交换的次数。

乍一看是要优化算法。实际上，无序序列在降序排序过程中发生的元素交换次数，正是原序列的各元素 逆序数之和。

  1. 最大元素个数在 int32 范围内；
  2. 单个元素的范围为 [−1018-10^{18}, 101810^{18}]（约 [−260-2^{60}, 2602^{60}]），远超 int32 范围，需要用 int64 来存储；

因此只需求输入数列的逆序数和即可，算法选择归并排序。

判断一个数是否为质数——优化常见O(sqrt(n)/2)复杂度算法存在的问题

· 阅读需 2 分钟
El Syzomnia
El Syzomnia
El Furnia 所有者

O(n2)O(\dfrac{\sqrt n}{2}) 复杂度算法作为常见 O(n)O(\sqrt n) 复杂度算法的优化版本，能够减少后者的一半复杂度，但常见优化算法或多或少存在一些问题：有的无法对个位数正确判断、有的无法对负数正确判断……

这篇博客将给出一种优化版本解决提到的问题。

初见递归｜递归函数求猴子吃桃——常规吃桃问题的一种变形

· 阅读需 3 分钟
El Syzomnia
El Syzomnia
El Furnia 所有者

题目​

题面描述

猴子在第一天摘了若干个桃子（奇数），吃掉了桃子的一半多一个，第二天吃掉了剩下桃子的一半多一个，以后每天都吃掉剩下桃子的一半多一个，直到第n天，桃子只剩1个，不再吃桃。

编写递归函数，猴子用day天吃到桃子只剩1个，则最开始有多少个桃子，如调用tao(3) 得到的返回值是7（第1天有7个桃子，第2天有3个桃子（猴子吃掉了7/2+1）,第3天剩余有1个桃子）。

函数接口定义：

int tao(int day);

i 是用户传入的参数,是int值，表示第i天； 函数调用结束后得到第i天剩余的桃子数量。

裁判测试程序样例：

在这里给出函数被调用进行测试的例子。例如：

#include<iostream>
using namespace std;
int tao(int day);
int main()
{
 int day;
 cin >> day;
 int n = tao(day);
 cout << n;
 return 0;
}
/* 请在这里填写答案 */

输入样例1:

3

输出样例1:

7

输入样例2:

4

输出样例2:

15

输入样例3:

5

输出样例3:

31

时间限制: 400 ms
内存限制: 64 MB

计算圆柱体的表面积和体积——利用%g对输出进行控制

· 阅读需 2 分钟
El Syzomnia
El Syzomnia
El Furnia 所有者

题目​

题面描述

编写程序，键盘输入圆柱体的底面半径和高，计算并输出圆柱体的表面积和体积（圆周率按3.14计）。

输入格式:

在一行中输入圆柱体的底面半径和高。

输出格式:

对每一组输入，在两行中分别输出表面积S和体积V。

输入样例:

在这里给出一组输入。例如：

1 1.21

输出样例:

在这里给出相应的输出。例如：

S=13.8788
V=3.7994