每日一题之召唤数学精灵

问题描述

数学家们发现了两种用于召唤强大的数学精灵的仪式，这两种仪式分别被称为累加法仪式 A(n) 和累乘法仪式 B(n)。

累加法仪式 A(n) 是将从 1 到 n 的所有数字进行累加求和，即：A(n)=1+2+⋯+n累乘法仪式 B(n) 则是将从 1 到 n 的所有数字进行累乘求积，即：B(n)=1×2×⋯×n据说，当某个数字 ii 满足 A(i)−B(i)能被 100 整除时，数学精灵就会被召唤出来。

现在，请你寻找在 1 到 2024041331404202 之间有多少个数字 i，能够成功召唤出强大的数学精灵。

答案提交

这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

#include <iostream>
using namespace std;
long long addsum(int n){
  long long sum=0;
  for(long long i=1;i<=n;i++){
    sum+=i;
  }
  return sum;
}
long long pulsum(int n){
  long long sum=1;
  for(long long i=1;i<=n;i++){
    sum*=i;
  } 
  return sum;
}
int main()
{
  // 请在此输入您的代码
  for(long long i=1;i<5000;i++){
    if((addsum(i)-pulsum(i))%100==0){
      cout<<i<<" ";
    }
  }
  return 0;
}

这道题给出的数据太大，直接用题目给的数据找根本跑不出来代码。那么当数据量太大的时候就只能去找规律，我选择找5000以内的数，后面发现其实当i=21的时候就已经超过long long的数据范围了。

继续思考，阶乘的话，其实当i>=10的时候就一定能被100整除，因为2*5*10的等于100，再乘多少都一样，所以我们只需要去找出10以内的数，满足条件的。

#include <iostream>
using namespace std;
long long addsum(int n){
  long long sum=0;
  for(long long i=1;i<=n;i++){
    sum+=i;
  }
  return sum;
}
long long pulsum(int n){
  long long sum=1;
  for(long long i=1;i<=n;i++){
    sum*=i;
  } 
  return sum;
}
int main()
{
  // 请在此输入您的代码
  for(long long i=1;i<10;i++){
    if((addsum(i)-pulsum(i))%100==0){
      cout<<i<<" ";
    }
  }
  return 0;
}

满足条件的只有1和3，然后其实可以不用管阶乘，直接去找求和之后能被100整除的，10到1000满足条件的数有这么多。

然后找规律，24，75,99，00，每200个数里面有4个，根据以下规律就很好找了。

还有大佬推导了一段公式：