牛客-小y的盒子

题目传送门

-------------------稍加观察就会发现,4- 1就是题目要的答案。至于为什么,看官方的题解。不过这个n非常的大,用正常快速幂解决不了。这道题我学到的就是解决幂非常大的情况。

官方题解传送门

sol1:之前好像做过一道类似的题目,想不出来,在群里看到网友发了一个名词叫十进制快速幂。然后根据这个名字自己意淫通了。一般的快速幂是把幂当成二进制用位运算进行处理。但是字符串不方便进行二进制位运算,不过用同样的方式进行十进制操作就很方便了。如果对二进制快速幂理解够深刻还是很好明白的;

  • 十进制快速幂
    #include "bits/stdc++.h"
    using namespace std;
    const int MAXN = 1e5 + 10;
    char s[MAXN]; int p;
    int quick_pow_2(int n, int k) {
        int ans = 1;
        while (k) {
            if (k & 1) ans = 1LL * ans * n % p;
            n = 1LL * n * n % p;
            k >>= 1;
        }
        return ans;
    }
    int quick_pow_10(int n, char* k) {
        int ans = 1;
        for (int i = strlen(k) - 1; i >= 0; i--) {
            ans = 1LL * ans * quick_pow_2(n, k[i] ^ '0') % p;
            n = quick_pow_2(n, 10);
        }
        return ans;
    }
    int main() {
        int t;
        scanf("%d", &t);
        while (t--) {
            scanf("%s%d", s, &p);
            printf("%d\n", (quick_pow_10(4, s) + p - 1) % p);
        }
        return 0;
    }

     

sol2:解决这样的问题,更主流的方法还是欧拉降幂,我也是刚学的。看官方题解中的代码不是用十进制快速幂做的,于是学习了一下。原先只知道费马小定理,现在感觉费马小定理就是欧拉降幂的一种特殊情况。原理搞不懂,结论就是:a ^ b % c = a ^ (b %  euler(c) + euler(c)) % c。其中euler(c)表示小于c且和c互质的正整数的个数。

  • 欧拉降幂
    #include "bits/stdc++.h"
    using namespace std;
    const int MAXN = 1e5 + 10;
    char s[MAXN]; int p;
    int euler(int n) {
        int ans = n;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                ans = ans / i * (i - 1);
                while (n % i == 0)
                    n /= i;
            }
        }
        if (n != 1) ans = ans / n * (n - 1);
        return ans;
    }
    int quick_pow(int n, int k) {
        int ans = 1;
        while (k) {
            if (k & 1) ans = 1LL * ans * n % p;
            n = 1LL * n * n % p;
            k >>= 1;
        }
        return ans;
    }
    int main() {
        int t;
        scanf("%d", &t);
        while (t--) {
            scanf("%s%d", s, &p);
            int m = euler(p), k = 0; 
            for (int i = 0; s[i]; i++)
                k = (k * 10LL + s[i] - '0') % m;
            printf("%d\n", (quick_pow(4, k + m) - 1 + p) % p);
        }
        return 0;
    }

     

上一篇:我也写个快速排序


下一篇:快速排序