BJTUOJ 1924 — jerry99的数列

题目

jerry99的数学能力很强，经常会研究一些复杂的数学问题。

已知数列 a1,a2,…,an，其中 ai 是最接近 √i 的整数。

jerry99想知道 a1×a2×…×an 的结果，但是他的作业太多了，你能帮帮他吗？

由于结果可能很大，请将结果对 10^9+7 取模。

题目链接

数学公式乱码了，建议大家看原题。
https://citel.bjtu.edu.cn/acm/problem/1924

输入数据

第一行为一个整数 T (1≤T≤100) ，表示一共有 T 组数据。
对于每组数据：
输入一行，包含一个整数 n (1≤n≤109)。

输出数据

对于每组数据，输出一行一个整数，表示 Π(n i=1)ai(mod10^9+7)。

样例输入

6
1
2
3
4
5
998244353

样例输出

1
1
2
4
8
361817674

样例说明

对于前 5 组数据：
a1=1
a2=1
a3=2
a4=2
a5=2
故可求得相应结果。

问题分析

观察题目给出的样例说明，就会想到这道题目有可能是存在数学规律的。于是我们稍微多计算几个 ai 的值，如下：

1 1 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 4 4

2个1，4个2，6个3，8个4
到这里就可以确定存在数学规律，即会按顺序出现 2x 个 x
对于整数 n，我们从 x=1 开始枚举求和，直到和 sum 最终等于 n。当然，最后一个 2x + sum 不一定正好等于 n，需要判断一下。
求 x 的 2x 次幂，需要用快速幂来缩短时间。
核心代码如下：

sum = 0;
x = 1;
ans = 1;
while (sum < n)
{
    if (sum + 2 * x < n)
    {
        sum += 2 * x;
        ans = (ans * quickpow(x, 2 * x)) % mod;
        x++;
    }
    else
    {
        ans = (ans * quickpow(x, n - sum)) % mod;
        sum = n;
    }
}
cout << ans << endl;

AC代码

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;

long long quickpow(long long a, long long b)
{
    long long ans = 1, base = a;
    while (b != 0)
    {
        if (b & 1 != 0) //b的二进制最右一位为1
        {
            ans = (ans * base) % mod;
        }
        base = (base * base) % mod;
        b >>= 1;
    }
    return ans % mod;
}
int main()
{
    int t, n, i, x = 1, sum = 0;
    long long ans;
    cin >> t;
    while (t--)
    {
        cin >> n;
        sum = 0;
        x = 1;
        ans = 1;
        while (sum < n)
        {
            if (sum + 2 * x < n)
            {
                sum += 2 * x;
                ans = (ans * quickpow(x, 2 * x)) % mod;
                x++;
            }
            else
            {
                ans = (ans * quickpow(x, n - sum)) % mod;
                sum = n;
            }
        }
        cout << ans << endl;
    }
    return 0;
}