POJ1995 Raising Modulo Numbers

Description

People are different. Some secretly read magazines full of interesting girls’ pictures, others create an A-bomb in their cellar, others like using Windows, and some like difficult mathematical games. Latest marketing research shows, that this market segment was so far underestimated and that there is lack of such games. This kind of game was thus included into the KOKODáKH. The rules follow:

Each player chooses two numbersandand writes them on a slip of paper. Others cannot see the numbers. In a given moment all players show their numbers to the others. The goal is to determine the sum of all expressionsfrom all players including oneself and determine the remainder after division by a given number M. The winner is the one who first determines the correct result. According to the players’ experience it is possible to increase the difficulty by choosing higher numbers.

You should write a program that calculates the result and is able to find out who won the game.

每个人都是不同的。有人偷偷阅读那些满是漂亮女孩照片的杂志，有人则在地下室制造原子弹，还有人喜欢使用 Windows 系统，而有些人则热衷于解复杂的数学游戏。最新的市场调查显示，这一细分市场至今一直被低估，且此类游戏十分匮乏。因此，这类游戏被纳入了 KOKODáKH 之中。游戏规则如下：
每位玩家选择两个数字和，并将它们写在一张纸上。其他玩家无法看到这些数字。在指定时间点，所有玩家同时将自己的数字展示给其他人。目标是要算出包括自己在内的所有玩家所对应的表达式之和，并求出该总和除以某个固定数 M 后的余数。最先算出正确结果的人即为胜者。根据玩家的体验，通过选择更大的数字可以提高游戏的难度。
你需要编写一个程序来计算结果，并判断谁是游戏的赢家。

Input

The input consists of Z assignments. The number of them is given by the single positive integer Z appearing on the first line of input. Then the assignements follow. Each assignement begins with line containing an integer M (). The sum will be divided by this number. Next line contains number of players H (). Next exactly H lines follow. On each line, there are exactly two numbersandseparated by space. Both numbers cannot be equal zero at the same time.

输入包含 Z 个分配任务。其数量由输入第一行给出的正整数 Z 决定。随后便是这些分配任务的具体内容。每个任务的第一行会给出一个整数 M（），总和需要被这个数除。下一行会给出玩家数量 H（）。紧接着会有 H 行数据，每行包含两个用空格分隔的数字和，且这两个数字不能同时为零。

Output

For each assingnement there is the only one line of output. On this line, there is a number, the result of expression

对于每个任务，仅输出一行结果。这一行包含一个数字，即表达式的计算结果。

Sample Input

3
16
4
2 3
3 4
4 5
5 6
36123
1
2374859 3029382
17
1
3 18132

Sample Output

1
2
3

2
13195
13

Limit

Time Limit	Memory Limit
1000MS	30000K

Analysis

朴素地，按照题目描述实现计算：

#include <iostream>
using LL = long long;

int z, m, h, a, b;
int main () {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    std::cin >> z;
    while(z--) {
        LL ans = 0;
        std::cin >> m >> h;
        while(h--) {
            std::cin >> a >> b;
            LL res = a;
            while(--b) res = res * a % m;
            ans = (ans + res) % m;
        }
        std::cout << ans << '\n';
        
    }
}

会发现 TLE 了，如何优化运行时间呢？分析核心代码：

while(h--) {
    std::cin >> a >> b;
    LL res = a;
    while(--b) res = res * a % m;
    ans = (ans + res) % m;
}

时间复杂度为。

故总的时间复杂度为，尽管题目并没有给出、的数据范围，但、部分无法优化时间，可以判断优化点在部分。对于快速求幂，有「快速幂」算法，接下来将对该算法进行推导介绍。

Algorithm

快速幂可从二进制展开理解，若：

则：

每个都可以由前一个平方得到。比如：

那么算法实现从指数的最低位开始处理：

while(b) {
    if(b & 1) res = res * t % p;
    t = t * t % p;
    b >>= 1;
}

这里，t 表示当前对应的幂；b & 1 检查当前最低位是否为，若是，就把 t 乘入 res。之后将 t 平方以得到下一位对应的幂，再右移 b，处理下一位。每次乘法后取模不会改变最终余数，因此可以避免中间结果不断变大。

指数每轮右移一位，循环次数等于的二进制位数，所以单次求幂的时间复杂度为，额外空间复杂度为。

那本题可以这样实现：

#include <iostream>
using LL = long long;

LL power(LL a, LL b, LL p) {
    LL t = a * 1ll, res = 1ll % p;
    while(b) {
        if(b & 1) res = res * t % p;
        t = t * t % p;
        b >>= 1;
    }
    return res;
}

int z, m, h, a, b;
int main () {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    std::cin >> z;
    while(z--) {
        LL ans = 0;
        std::cin >> m >> h;
        while(h--) {
            std::cin >> a >> b;
            ans = (ans + power(a, b, m)) % m;
        }
        std::cout << ans << '\n';
        
    }
}

res = 1ll % p 是为了在时，初值为，并能正确处理。

Template

template <class T>
T power(T a, T b, T p) {
    T t = (T)a % p, res = (T)1 % p;
    
    while(b) {
        if(b & 1) res = res * t % p;
        t = t * t % p;
        b >>= 1;
    }
    
    return res;
}

power() 要求、。

Ref

1995 – Raising Modulo Numbers

Loading...