A1947 An Olympian Math Problem

文章目录

一、A1947 An Olympian Math Problem

总结

一、A1947 An Olympian Math Problem

本题链接：A1947 An Olympian Math Problem述

题目：

Alice, a student of grade 66, is thinking about an Olympian Math problem, but she feels so despair that she cries. And her classmate, Bob, has no idea about the problem. Thus he wants you to help him. The problem is:

Then S module n is ____________

You are given an integer n.

You have to calculate S modulo n.

Input

Output

For each test case, print an integer S modulo n.

Hint

样例输入

2

2

3

样例输出

1

2

本博客给出本题截图：

分析

本题正常思路写下的代码：（第一次写的时候的代码）

#include <iostream>
using namespace std;
int ft(int n)
{
    int res = 1;
    for (int i = 2; i <= n; i ++ )
        res *= i;
    return res;
}
int f(int n)
{
    int cnt = 0;
    for (int i = 1; i < n; i ++ )
        cnt += i * ft(i);
    return cnt;
}
int main()
{
    int m;
    cin >> m;
    while (m -- )
    {
        int n;
        cin >> n;
        cout << f(n) % n << endl;
    }
    return 0;
}

这个代码交上去之后爆TLE

看到之后想到可能是三重循环的原因（虽然拆成了三个函数，但是其实是三重循环），想到先求一下阶乘，存到数组中，直接查找就可以省去一重循环，再注意到n的范围的时候立刻又否定了这个想法，百思不得其解后看了下佬写的代码，才发现这个题的背后是一道找规律的题目，读者不妨用TLE的代码去打表看一下输出结果始终都是n - 1，故正解AC代码为

AC代码

#include <iostream>
using namespace std;
typedef long long LL;
int main()
{
    int m;
    cin >> m;
    while (m -- )
    {
        LL n;
        cin >> n;
        cout << n - 1 << endl;
    }
    return 0;
}

总结

看了佬写的题解才意识到这是一道找规律的题目，第一次遇到这种题目，有趣之余要注意数学类题目的灵活.