NEFU离散数学实验PBL

- 日理万妓 2024-04-17 13:40 39阅读 0赞

### 1.青蛙的约会 ###

> Description
> 
>     两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。 
>     我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。
> 
> Input
> 
>     输入只包括一行5个整数x，y，m，n，L，其中x≠y < 2000000000，0 < m、n < 2000000000，0 < L < 2100000000。
> 
> Output
> 
>     输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行"Impossible"
> 
> Sample Input
> 
>     1 2 3 4 5
> 
> Sample Output
> 
>     4

测试数据模拟

![9bc73b5a7d474d2d86bb44cfb82a104b.png][] ![9e6a9a6da9f04ce29ff58096990dfff1.jpg][]

#include <iostream>
    
    using namespace std;
    
    #define  LL long long
    
    /*
        x:青蛙a的起点
        y:青蛙b的起点
        m:青蛙a一次能跳多远
        n:青蛙b一次能跳多远
        L:一圈的距离
    */
    LL x, y, m, n, l; 
    
    LL exgcd(LL a,LL b,LL &x,LL &y){//扩展欧几里得算法
        if(b==0){
            x=1,y=0;
            return a;
        }
        LL d=exgcd(b,a%b,y,x);
        y-=a/b*x;
        return d;
    }
    int main()
    {
    
        while(cin >> x >> y >> m >> n >> l){ 
    
            LL t = ((y - x) % l + l) % l; // 计算 t 的值，保证 t 为正数
    
            LL a = ((m - n) % l + l) % l; // 计算 a 的值，保证 a 为正数
    
            LL b = l;
    
            LL d = exgcd(a, b, x, y); // 调用 exgcd 函数，求解 a 和 b 的最大公约数，同时更新 x 和 y 的值
    
            if(t % d) cout << "Impossible" << endl; // 如果 t 不能整除 d，即永远也碰不到，输出 "Impossible"
    
            else{
                x = ((x * t / d) % (b / d) + b / d) % (b / d); 
                /*
                    计算青蛙a在t时间内从起点x跳到终点y所需的最小步数
    
                    % (b / d)：取模运算，用于确保跳跃距离不超过一圈的距离b。因为每圈的距离为b，所            
                    以需要将跳跃距离限制在b以内。
    
                    + b / d：加上一圈的距离的一半，以确保跳跃距离始终在起点和终点之间。
    
                     % (b / d)：再次取模运算，确保最终的跳跃距离仍然在一圈的距离b以内。
                */
    
                cout << x << endl; 
            }
        }
    
        return 0; 
    }

### 2.五指山 ###

> Description
> 
>     西游记中孙吾空大闹天宫，如来佛祖前来降伏他，说道：“我与你打个赌赛；你若有本事，一筋斗打出我这右手掌中，算你赢，再不用动刀兵苦争战，就请玉帝到西方居住，把天宫让你；若不能打出手掌，你还下界为妖，再修几劫，却来争吵。”
>     那大圣闻言，暗笑道：“这如来十分好呆！我老孙一筋斗去十万八千里。他那手掌，方圆不满一尺，如何跳不出去？”急发声道：“既如此说，你可做得主张？”佛祖道：“做得！做得！”伸开右手，却似个荷叶大小。那大圣收了如意棒，抖擞神威，将身一纵，站在佛祖手心里，却道声：“我出去也！”你看他一路云光，无影无形去了。大圣行时，忽见有五根肉红柱子，撑着一股青气。他道：“此间乃尽头路了。这番回去，如来作证，灵霄殿定是我坐也。”翻转筋斗云，径回本处，站在如来掌：“我已去，今来了。你教玉帝让天宫与我。”
>     如来骂道：“你正好不曾离了我掌哩！”大圣道：“你是不知。我去到天尽头，见五根肉红柱，撑着一股青气，我留个记在那里，你敢和我同去看么？”如来道：“不消去，你只自低头看看。”那大圣睁圆火眼金睛，低头看时，原来佛祖右手中指写着“齐天大圣，到此一游。”大圣大吃了一惊道：“有这等事！有这等事！我将此字写在撑天柱子上，如何却在他手指上？莫非有个未卜先知的法术？我决不信！不信！等我再去来！”
>     好大圣，急纵身又要跳出，被佛祖翻掌一扑，把这猴王推出西天门外，将五指化作金、木、水、火、土五座联山，唤名“五行山”，轻轻的把他压住。
>         我们假设佛祖的手掌是一个圆圈（所以任凭大圣一个筋斗云十万八千里也是飞不出其手掌心），圆圈的长为n，逆时针记为：0，1，2，…,n-1，而大圣每次飞的距离为d.现在大圣所在的位置记为x,而大圣想去的地方在y。现在要你告诉大圣至少要多少筋斗云才能到达目的地。
> 
> Input
> 
>     有多组测试数据。
>     第一行是一个正整数T，表示测试数据的组数。
>     每组测试数据包括一行，四个非负整数，n（2 < n < 10^9），表示如来手掌圆圈的长度；d(0 < d < n),筋斗所能飞的距离；x(0 <= x < n),大圣的初始位置；y(0 <= y < n)，大圣想去的地方。
>        注意孙悟空的筋斗云只沿着逆时针方向翻。
> 
> Output
> 
>     对于每组测试数据，输出一行，给出大圣最少要翻多少个筋斗云才能到达目的地。如果无论翻多少个筋斗云也不能到达，输出“Impossible”.
> 
> Sample Input
> 
>     2
>     3 2 0 2
>     3 2 0 1
> 
> Sample Output
> 
>     1
>     2

测试数据模拟

![b1dd3cacde8d4b0f820063dcb99ac1d5.jpg][]![53924c9dec5645ef91888e4f4fa6db25.jpg][]

#include<iostream>
    #include<algorithm>
    #include<cstdio>
    using namespace std;
    
    typedef long long LL;
    
    /*
        x:大圣的初始位置
        y:大圣的目的地·
        n:如来手掌圆圈的长度
        d:筋斗所能飞的距离 
    
    */
    
    LL n,d,x,y,q,p;
    
    LL exgcd(LL a,LL b,LL &x,LL &y){//扩展欧几里得算法
        if(b==0){
            x=1,y=0;
            return a;
        }
        LL d=exgcd(b,a%b,y,x);
        y-=a/b*x;
        return d;
    }
    
    int main(){
        int T;
        scanf("%d",&T);
        while(T--){
            
            cin>>n>>d>>x>>y;
            LL t = ((y-x)%n+n)%n;// 计算 t 的值，保证 t 为正数
            int gcd = exgcd(n,d,q,p);
            if((t)%gcd){
                cout << "Impossible" << endl;
            }else{
                
                p*=t/gcd;
                n/=gcd;
                cout<<(p%n+n)%n<<endl;
                //计算大圣从初始位置到目的地的最短距离
            }
        }
        return 0;
    }

### 3.Fight 2018 ###

> Description
> 
>     由于今年是2018年，所以BD对2018这个数字深有研究，最近又开始研究2018的因子，她想知道2018的因子和是多少，可是她觉得这个问题太简单了，没有什么挑战性，她想让你求2018^n 的因子和是多少，可是由于结果太大了，所以要求对499取模。
> 
> Input
> 
>     输入数据包含多个测试实例，每个测试实例的输入只包含一个正整数n（1<=n<=1e20）。输入0的时候结束。
> 
> Output
> 
>     对应于每一个输入，请输出对应的答案。
> 
> Sample Input
> 
>     1
>     0
> 
> Sample Output
> 
>     36

> 计算2018^n 的因子和，首先要知道2018的质因数分解，即2018=2\*1009。根据因子和的公式1，如果一个数n可以写成![eq?n%3Dp\_1%5E%20%7Ba\_1%7Dp\_2%5E%20%7Ba\_2%7D...p\_k%5E%20%7Ba\_k%7D][eq_n_3Dp_1_5E_20_7Ba_1_7Dp_2_5E_20_7Ba_2_7D...p_k_5E_20_7Ba_k_7D]\}的形式，其中![eq?p\_i][eq_p_i]是不同的质数，![eq?a\_i][eq_a_i]是正整数，那么n的因子和是：![eq?f%20%28n%29%3D%5Cprod\_%20%7Bi%3D1%7D%5Ek%20%7Bp\_i%5E%20%7Ba\_i&plus;1%7D-1%5Cover%20p\_i-1%7D][eq_f_20_28n_29_3D_5Cprod_20_7Bi_3D1_7D_5Ek_20_7Bp_i_5E_20_7Ba_i_plus_1_7D-1_5Cover_20p_i-1_7D]
> 
> 所以，![eq?2018%5En][eq_2018_5En] 的因子和是：
> 
> ![eq?f%20%282018%5En%29%3D%20%7B2%5E%20%7Bn&plus;1%7D-1%5Cover%202-1%7D\*%20%7B1009%5E%20%7Bn&plus;1%7D-1%5Cover%201009-1%7D%20%3D%20%282%5E%20%7Bn&plus;1%7D-1%29\*%20%281009%5E%20%7Bn&plus;1%7D-1%29][eq_f_20_282018_5En_29_3D_20_7B2_5E_20_7Bn_plus_1_7D-1_5Cover_202-1_7D_20_7B1009_5E_20_7Bn_plus_1_7D-1_5Cover_201009-1_7D_20_3D_20_282_5E_20_7Bn_plus_1_7D-1_29_20_281009_5E_20_7Bn_plus_1_7D-1_29]
> 
> 这个结果可能非常大，所以题目要求对499取模。这里可以用中国剩余定理2，即如果两个数m和n互质，那么对于任意的a和b，方程组
> 
> ![eq?x%5Cequiv%20a%5Cpmod%20m][eq_x_5Cequiv_20a_5Cpmod_20m]
> 
> ![eq?x%5Cequiv%20b%5Cpmod%20n][eq_x_5Cequiv_20b_5Cpmod_20n]
> 
> 有唯一解x，且![eq?x%5Cequiv%20a%5Cpmod%20%7Bmn%7D][eq_x_5Cequiv_20a_5Cpmod_20_7Bmn_7D]
> 
> 因为2018和499互质，所以我们可以先分别计算2018^n 对499取模的结果，记为a，以及2018的因子和对499取模的结果，记为b，然后用中国剩余定理求解x，即2018^n 的因子和对499取模的结果。

> 举例
> 
> 计算2018^n 对499取模的结果，可以用快速幂算法3，即将n转换为二进制，然后从低位到高位依次计算2018的幂次，每次对499取模，最后累乘得到结果。例如，如果n=5，那么n的二进制是101，所以
> 
> 2018^5 mod 499
> 
> = (2018^1 mod 499) \* (2018^4 mod 499)
> 
> = (2018 mod 499) \* ((2018^2 mod 499)^2 mod 499)
> 
> = (202 mod 499) \* (((202^2 mod 499)^2 mod 499)
> 
> = (202 mod 499) \* ((408^2 mod 499) mod 499)
> 
> = (202 mod 499) \* (64 mod 499)
> 
> = 12928 mod 499
> 
> = 433

#include <iostream>
    using namespace std;
    
    // 定义模数常量
    const int MOD = 499;
    
    // 快速幂函数，计算 a^b % mod 的值
    long long pow_q(int a, __int128 b, int mod) {
        long long m = 1;
        while (b > 0) {
            if (b % 2 == 1) {
                m = (m * a) % mod;  // 如果b的二进制最低位为1，计算m乘以a再对mod取模
            }
            a = (a * a) % mod;  // a自乘一次再对mod取模
            b /= 2;  // b右移一位，相当于除以2
        }
        return m;  // 返回计算结果
    }
    
    // 快读
    inline __int128 read() {
        __int128 x = 0, f = 1;
        char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-')
                f = -1;  
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            x = x * 10 + ch - '0';  
            ch = getchar();
        }
        return x * f;  
    }
    
    //快写
    inline void print(__int128 x) {
        if (x < 0) {
            putchar('-');  
            x = -x;  
        }
        if (x > 9)
            print(x / 10);  
        putchar(x % 10 + '0');  
    }
    
    int main() {
        __int128 n;
        while (n = read()) {  
            if (n == 0) return 0;  
            // 计算数列的和
            long long sum = (pow_q(2, n + 1, MOD) - 1) * pow_q(2 - 1, MOD - 2, MOD) % MOD;  // 计算第一个乘积
            sum = (sum * (pow_q(1009, n + 1, MOD) - 1) * pow_q(1009 - 1, MOD - 2, MOD)) % MOD;  // 计算第二个乘积
            cout << sum << endl;  
        }
        return 0;
    }

[9bc73b5a7d474d2d86bb44cfb82a104b.png]: https://img-blog.csdnimg.cn/9bc73b5a7d474d2d86bb44cfb82a104b.png
[9e6a9a6da9f04ce29ff58096990dfff1.jpg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/12/f3aa172b209d4668aa5ffd0731c7e12f.jpg
[b1dd3cacde8d4b0f820063dcb99ac1d5.jpg]: https://img-blog.csdnimg.cn/b1dd3cacde8d4b0f820063dcb99ac1d5.jpg
[53924c9dec5645ef91888e4f4fa6db25.jpg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/12/30eee4b8c1b447d7ac0041ac7901e923.jpg
[eq_n_3Dp_1_5E_20_7Ba_1_7Dp_2_5E_20_7Ba_2_7D...p_k_5E_20_7Ba_k_7D]: https://latex.csdn.net/eq?n%3Dp_1%5E%20%7Ba_1%7Dp_2%5E%20%7Ba_2%7D...p_k%5E%20%7Ba_k%7D
[eq_p_i]: https://latex.csdn.net/eq?p_i
[eq_a_i]: https://latex.csdn.net/eq?a_i
[eq_f_20_28n_29_3D_5Cprod_20_7Bi_3D1_7D_5Ek_20_7Bp_i_5E_20_7Ba_i_plus_1_7D-1_5Cover_20p_i-1_7D]: https://latex.csdn.net/eq?f%20%28n%29%3D%5Cprod_%20%7Bi%3D1%7D%5Ek%20%7Bp_i%5E%20%7Ba_i&plus;1%7D-1%5Cover%20p_i-1%7D
[eq_2018_5En]: https://latex.csdn.net/eq?2018%5En
[eq_f_20_282018_5En_29_3D_20_7B2_5E_20_7Bn_plus_1_7D-1_5Cover_202-1_7D_20_7B1009_5E_20_7Bn_plus_1_7D-1_5Cover_201009-1_7D_20_3D_20_282_5E_20_7Bn_plus_1_7D-1_29_20_281009_5E_20_7Bn_plus_1_7D-1_29]: https://latex.csdn.net/eq?f%20%282018%5En%29%3D%20%7B2%5E%20%7Bn&plus;1%7D-1%5Cover%202-1%7D*%20%7B1009%5E%20%7Bn&plus;1%7D-1%5Cover%201009-1%7D%20%3D%20%282%5E%20%7Bn&plus;1%7D-1%29*%20%281009%5E%20%7Bn&plus;1%7D-1%29
[eq_x_5Cequiv_20a_5Cpmod_20m]: https://latex.csdn.net/eq?x%5Cequiv%20a%5Cpmod%20m
[eq_x_5Cequiv_20b_5Cpmod_20n]: https://latex.csdn.net/eq?x%5Cequiv%20b%5Cpmod%20n
[eq_x_5Cequiv_20a_5Cpmod_20_7Bmn_7D]: https://latex.csdn.net/eq?x%5Cequiv%20a%5Cpmod%20%7Bmn%7D