学习笔记：乘法溢出问题

学习笔记：乘法溢出问题

1、3n+1问题
对于任意大于1的自然数，若n为奇数就将n变为3n+1，否则变为n的一半。当n变为1时，进行了多少次变换？
程序一：

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
    int n;
    int count=0;
    cin>>n;
    while(n>1)
    {
        if(n%2==0)
            n=n/2;
        else
            n=3*n+1;
        count++;
    }
    cout<<count<<endl;
    return 0;
}
此程序看似没问题，但当输入比int上界小一点点的n时，会乘法溢出。
可以用以下程序解决

程序二：

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
    long long n;
    int count=0;
    cin>>n;
    while(n>1)
    {
        if(n%2==0)
            n=n/2;
        else
            n=3*n+1;
        count++;
    }
    cout<<count<<endl;
    return 0;
}

二、阶乘之和问题
计算S=1!+2!+……+n!的末六位。
程序一：

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
    int n;
    int sum=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int factorial=1;
        for(int j=i;j>=1;j--)
            factorial=factorial*j;
        sum+=factorial;
    }
    printf("%d\n",sum%1000000);
    return 0;
}

当输入n=100时，输出-961703，说明乘法又溢出了，要解决这个问题，需要一个数学知识：计算只包含乘法加法减法的表达式时，对表达式除余，可以对每步计算除余，结果是不变的。
程序二：

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
    int n;
int sum=0;
const int MOD=1000000;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int factorial=1;
        for(int j=i;j>=1;j--)
            factorial=factorial*j%MOD;
        sum+=factorial%MOD;
    }
    printf("%d\n",sum);
    return 0;
}