ACM程序设计课内实验（3）循环节问题

曾经终败给现在 2024-04-17 13:41 26阅读 0赞

## 1.[数字序列][Link 1] ##

> 描述  
> 数字序列定义如下：  
> f（1）=1，f（2）=1，f（n）=（A\*f（n-1）+B\*f（n-2））mod 7。  
> 给定A、B和n，你要计算f（n）的值。  
> 输入  
> 输入由多个测试用例组成。每个测试用例在一行中包含3个整数A、B和n（1<=A、B<=1000、1<=n<=100000000）。三个零表示输入结束，不处理此测试用例。  
> 输出  
> 对于每个测试用例，在一行上打印f（n）的值。  
> 样本输入  
> 1 1 3  
> 1 2 10  
> 0 0  
> 样本输出  
> 2.  
> 5.

常规解法

#include <iostream>
    #include <vector>
    using namespace std;
    
    int main() {
        vector<long long> dp(100000001, -1);
        int A, B, n;
    
        while (cin >> A >> B >> n) {
            if (A == 0 && B == 0 && n == 0) {
                break;
            }
    
            dp[1] = 1;
            dp[2] = 1;
            for (int i = 3; i <= n; i++) {
                dp[i] = (A * dp[i - 1] + B * dp[i - 2]) % 7;
            }
    
            cout << dp[n] << endl;
        }
    
        return 0;
    }

由于数据太大，wa了

![d901c3638c024a2e8afa228460ed61f7.png][]

#include <bits/stdc++.h>
    using namespace std;
    int res[1000]; // 定义一个数组用于存储计算结果
    
    int main()
    {
        res[1]=res[2]=1; // 初始化数组的前两个值为1
        int a,b,n; // 定义输入的三个整数A、B和n
        while(cin>>a>>b>>n) // 循环读取输入
        {
            if(a==0&&b==0&&n==0) // 如果输入为三个0，则结束循环
                break;
            if(n==1||n==2) // 如果n为1或2，直接输出结果
                cout<<res[n]<<endl;
            else
            {
                int i;
                for(i=3;i<30;i++) // 自动找循环节
                {
                    res[i]=(a*res[i-1]+b*res[i-2])%7; // 根据公式计算结果并取模
                    if(res[i]==1&&res[i-1]==1) // 只将一个循环节存入数组
                        break;
                }
                n=n%(i-2); // 注意循环节的下标，输出会造成些问题
                if(n==0)
                    cout<<res[i-2]<<endl;
                else
                    cout<<res[n]<<endl;
            }
        }
        return 0;
    }

## 2.[昨日重现][Link 2] ##

> #### Description ####
> 
>     兴安黑熊在高中学习数学时，曾经知道这样一个公式：f(n)=1^2+2^2+3^2+.......+n^2,这个公式是可以化简的，化简后的结果是啥它却忘记了，也许刚上大二的你能记得。现在的问题是想要计算f(n)对1007取余的值，你能帮帮他吗？
> 
> #### Input ####
> 
>     输入数据有多组（不超过100组），每组一个数n. (1<=n <=1,000,000,000).
> 
> #### Output ####
> 
>     输出f(n)对1007取余的值。
> 
> #### Sample Input ####
> 
>     3
>     4
>     100
> 
> #### Sample Output ####
> 
>     14
>     30
>     1005

常规算法

#include <iostream>
    using namespace std;
    
    const int MOD = 1007;
    
    int main() {
        int n;
        while (cin >> n) {
            long long sum = 0;
            for (int i = 1; i <= n; ++i) {
                sum = (sum + (long long)i * i) % MOD;
            }
            cout << sum << endl;
        }
        return 0;
    }

#### 取模公式 ####

> 当一个表达式对一个数取余的时候大概率存在周期，一般在三倍取模的数之内
> 
> (a+b)%c=(a%c+b%c)%c  
> (a*b)%c=((a%c)*(b%c))%c  
> ab%c=(a%c)b%c

#include <bits/stdc++.h>
    using namespace std;
    int main()
    {
        long long int n;
        while(cin>>n)
        {
            long long int n1=n,n2=n+1,n3=2*n+1;
            long long int res;
            //运用公式F(n)=(1/6*n*(n+1)*(2n+1))%1007
            //对1/6的处理，拆成1/2*1/3，由题意一定能整除
            if(n1%2==0)
                n1=n1/2;
            else
                n2=n2/2;
            if(n1%3==0)
                n1=n1/3;
            else if(n2%3==0)
                n2=n2/3;
            else
                n3=n3/3;
            res=((((n1%1007)*(n2%1007))%1007)*(n3%1007))%1007;//疯狂取模避免溢出
            cout<<res<<endl;
        }
        return 0;
    }

扩展欧几里得算法

//逆元做法
    #include <bits/stdc++.h>
    typedef long long LL;
    using namespace std;
    void Ex_gcd(LL a, LL b, LL &x, LL &y)
    {
        if(b == 0)//递归出口
        {x = 1;y = 0;return;}
        Ex_gcd(b, a%b, x, y);
        int t;
        t=x;
        x =y;
        y = t-(a/b)*y;
    }
    int main()
    {
        LL a,b,x,y,n,ans;
        Ex_gcd(6,1007,x,y);
        x=(x+1007)%1007;
        while(cin>>n)
        {
           ans=(n*(n+1))%1007;
           ans=(ans*(2*n+1))%1007;
           ans=(ans*x)%1007;//其实x=168
           cout<<ans<<endl;
        }
        return 0;
    }

> 首先调用 \`Ex\_gcd(6,1007,x,y)\` 求出 6在模 1007意义下的逆元 x，然后循环读入 n，计算 ![$f(n)$][f_n]的值。根据公式 ![$f(n)=\\frac\{n(n+1)(2n+1)\}\{6\}$][f_n_frac_n_n_1_2n_1_6]，可以将计算过程拆分为三个部分，每个部分计算完之后都对 1007取模，最后再乘起来，最终的结果也要对 1007取模。其中，n(n+1)(2n+1) 可以直接用乘法计算，而 ![$\\frac\{1\}\{6\}$][frac_1_6]的逆元就是 x，因此可以直接用 x$乘以 n(n+1)(2n+1)，而不必再除以6。

## 3.[Fibonacci Again][] ##

> 描述  
> 还有另一种斐波那契数：F（0）=7，F（1）=11，F（n）=F（n-1）+F（n-2）（n>=2）。  
> 输入  
> 输入由一系列行组成，每行包含一个整数n。（n<1000000）。  
> 输出  
> 如果3等分为F（n），则打印单词“是”。  
> 如果没有，请打印“否”字。  
> 样本输入  
> 0  
> 1.  
> 2.  
> 3.  
> 4.  
> 5.  
> 样本输出  
> no
> 
> no
> 
> yes
> 
> no
> 
> no
> 
> no

> **//余数循环节 1,2,0,2,2,1,0,1 每8个数为1个循环**

#include <stdio.h>
    
    //余数循环节 1,2,0,2,2,1,0,1  每8个数为1个循环
    
    int main()
    
    {
    
        int n;
    
        while(scanf("%d",&n)!=-1)
    
        {
    
           if(n%8==2||n%8==6)printf("yes\n");
    
           else printf("no\n");
    
        }
    
        return 0;
    
    }

## 4.[n!末尾有多少个0][n_0] ##

> #### Description ####
> 
>     计算N！末尾有多少个0
> 
> #### Input ####
> 
>     输入数据有多组，每组1行，每行1个数N（10 <= N <=100000000）
> 
> #### Output ####
> 
>     在一行内输出N！末尾0的个数。
> 
> #### Sample Input ####
> 
>     10
>     100
> 
> #### Sample Output ####
> 
>     2
>     24

> 观察个位数的乘法，仅有2*5能出现0  
> 因此把n！进行因式分解一对2*5末尾就有一个0  
> 而n！中2的数量一定大于5的数量  
> 因此即统计n！因式分解后出现几个5即可
> 
> **那么关键在于5的数量了那么该问题的实质是要求出1~100含有多少个5由特殊推广到一般的论证过程可得：  
> 1、 每隔5个，会产生一个0，比如 5， 10 ，15，20  
> 2 、每隔 5×5 个会多产生出一个0，比如 25，50，75，100  
> 3 、每隔 5×5×5 会多出一个0，比如125.**
> 
> **所以100！末尾有多少个零为：100/5+100/25=20+4=24那么1000！末尾有多少个零呢？**
> 
> **同理得： 1000/5+1000/25+1000/125=200+40+8=248**

#include <iostream>
    using namespace std;
    
    int main() {
        int N;
        while (cin >> N) {
            int count = 0;
            while (N >= 5) {
                count += N / 5;
                N /= 5;
            }
            cout << count << endl;
        }
        return 0;
    }

## 5.[斐波那契求模][Link 3] ##

> #### Description ####
> 
>     我们知道斐波那契数列的递推公式为f(n)=f(n-1)+f(n-2) n>=2 f(0)=0 f(1)=1;
>     那么，我们想知道f(n)%103的值是多少。
> 
> #### Input ####
> 
>     输入数据有多组，每组数据为一行，是一个整数n。
> 
> #### Output ####
> 
>     对于每组输入数据，输出一行，是一个整数，为f(n)%103的值。
> 
> #### Sample Input ####
> 
>     1
>     2
>     3
>     4
>     5
>     6
> 
> #### Sample Output ####
> 
>     1
>     1
>     2
>     3
>     5
>     8

#include <bits/stdc++.h>
    using namespace std;
    
    int main() {
        int f[208];
        f[0] = 0;
        f[1] = 1;
        for (int i = 2; i <= 207; i++) {
            f[i] = (f[i - 1] + f[i - 2]) % 103;
        }
        int n;
        while (cin >> n)
            cout << f[n % 208] << endl;
        return 0;
    }

## 6.[类似斐波那契求模][Link 4] ##

> #### Description ####
> 
>     现在有一个数列的递推公式是g(n)=3*g(n-1)+g(n-2).
>     g(1)=1,g(0)=0。
>     求g(n)%223的值。
> 
> #### Input ####
> 
>     输入数据有多组，每组数据为一行，是一个整数n。
> 
> #### Output ####
> 
>     对于每组输入数据，输出一行，是一个整数，为g(n)%223的值。
> 
> #### Sample Input ####
> 
>     1
>     2
>     3
>     4
>     5
>     6
> 
> #### Sample Output ####
> 
>     1
>     3
>     10
>     33
>     109
>     137

#include<bits/stdc++.h>
    using namespace std;
    
    int main() {
        int ans[448];
        ans[0] = 0;
        ans[1] = 1;
        for (int i = 2; i <= 447; i++) {
            ans[i] = 3 * ans[i - 1] + ans[i - 2];
            ans[i] %= 223;
        }
        int n;
        while (cin >> n)
            cout << ans[n % 448] << endl;
        return 0;
    }

## 7.[又见类似斐波那契求模][Link 5] ##

> #### Description ####
> 
>     如果有一个序列f(n)=a*f(n-1)+b*f(n-2),f(0)=0,f(1)=1。我们对于给定的系数a,b找到f(n)%107的值。
> 
> #### Input ####
> 
>     输入数据有多组，每组数据第一行有三个整数a,b(a>0,b>0),N，N代表接下来测试的数据数，接下来有N行，每行一个整数n。
> 
> #### Output ####
> 
>     对于在给定的系数a,b下对每个n输出每一个f(n)%107。
> 
> #### Sample Input ####
> 
>     3 1 6
>     1
>     2
>     3
>     4
>     5
>     6
> 
> #### Sample Output ####
> 
>     1
>     3
>     10
>     33
>     2
>     39

#include<bits/stdc++.h>
    using namespace std;
    
    int f[1000000];
    
    int main()
    {
        int a, b, N;
        while (cin >> a >> b >> N) {
            f[0] = 0;
            f[1] = 1;
            int i;
            for (i = 2;; i++) {
                f[i] = a * f[i - 1] + b * f[i - 2];
                f[i] %= 107;
                if (f[i] == 1 && f[i - 1] == 0)
                    break;
            }
            int len = i - 1;
            int ans[len];
            ans[0] = 0;
            ans[1] = 1;
            for (i = 2; i < len; i++) {
                ans[i] = a * ans[i - 1] + b * ans[i - 2];
                ans[i] %= 107;
            }
            while (N--) {
                int n;
                cin >> n;
                cout << ans[n % len] << endl;
            }
        }
        return 0;
    }

## 8.又见斐波那契 ##

> #### Description ####
> 
>     我们知道斐波那契数列的递推公式是f(n)=f(n-1)+f(n-2);现在老师给小明一个P，我们知道会有一个最小的m,使得f(n)%P=f(n+m)%P对每一个n成立，求出这个最小的m。
> 
> #### Input ####
> 
>     输入数据有多组，每组数据为一行，是一个整数P。(1<P<100000)。
> 
> #### Output ####
> 
>     对于每组输入数据，输出一行，是一个最小的整数m，使得f(n)%P=f(n+m)%P对每一个n成立。
> 
> #### Sample Input ####
> 
>     5 
>     11 
>     19 
>     61 
>     17
> 
> #### Sample Output ####
> 
>     20
>     10
>     18
>     60
>     36

#include<bits/stdc++.h>
    using namespace std;
    
    int f[1000000];
    
    int main()
    {
        int P;
        while(cin>>P){
            f[0]=0;
            f[1]=1;
            int i;
            for(i=2;;i++){
                f[i]=f[i-1]+f[i-2];
                f[i]%=P;
                if(f[i]==1&&f[i-1]==0)
                    break;
            }
            cout<<i-1<<endl;
        }
        return 0;
    }

[Link 1]: https://acm.webvpn.nefu.edu.cn/problemShow.php?problem_id=67
[d901c3638c024a2e8afa228460ed61f7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/12/15a9e52b3fda44918f8a8b8e45ac28b2.png
[Link 2]: http://acm.nefu.edu.cn/problemShow.php?problem_id=519
[f_n]: https://latex.csdn.net/eq?%24f%28n%29%24
[f_n_frac_n_n_1_2n_1_6]: https://latex.csdn.net/eq?%24f%28n%29%3D%5Cfrac%7Bn%28n&plus;1%29%282n&plus;1%29%7D%7B6%7D%24
[frac_1_6]: https://latex.csdn.net/eq?%24%5Cfrac%7B1%7D%7B6%7D%24
[Fibonacci Again]: https://acm.webvpn.nefu.edu.cn/problemShow.php?problem_id=70
[n_0]: http://acm.nefu.edu.cn/problemShow.php?problem_id=753
[Link 3]: https://acm.webvpn.nefu.edu.cn/problemShow.php?problem_id=576
[Link 4]: https://acm.webvpn.nefu.edu.cn/problemShow.php?problem_id=577
[Link 5]: https://acm.webvpn.nefu.edu.cn/problemShow.php?problem_id=579