## T1 - 大数因子数量

### TooY0ung 的思路

我们需要明白，判断因子的复杂度是 $O(\sqrt{n})$ 的。所以你直接暴力模拟也可以得到前 $16$ 个点的分数。

那么题目中要求算的是 $n * (n-1)$ 的因子数，这里你会遇到两个问题：

$1.$ $long long$ 也无法直接存下 $n*(n-1)$ 这么大的数。

$2.$ $O(\sqrt{n})$ 是 $O(\sqrt{n*(n-1)})$ 的，大小约为 $10^{12}$，时间复杂度超时。

所以还是需要分析性质。

显然，相邻的两个数是互质的，即，$gcd(n, n - 1) == 1$

假设有两个数 $a$ 和 $b$，如果两个数互质，$a*b$ 的因数数量 = $a$ 的因数数量 * $b$ 的因数数量。

这样我们是 $O(\sqrt{n})$ + $O(\sqrt{n - 1})$ 的复杂度了。

### TooY0ung 的满分代码
```cpp
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
#include<stack>
#include<sstream>
#include<set>
#include<time.h>
#include<stdlib.h>
#include<unordered_map>
#include<iomanip>
#include<bitset>
#include<cassert>
#define ll long long
#define ull unsigned long long
#define eps 1e-6
#define INF 1e9
#define delta 0.996
#define T 3000
#define pi acos(-1.0)
#define ld long double
const ll mod1 = 1e9 + 7;
const ll mod2 = 998244353;
const int maxn = 1e5 + 10;
const ll inf=1e18L;
using namespace std;
typedef pair<int,int> Pii;
typedef pair<ll,int> Pli;
typedef pair<ll,ll>P;
typedef pair<int, pair<int, int>>Pipii;
ll n;
ll solve(ll x)
{
    ll ans = 0;
    for(ll i = 1; i * i <= x; i++)
    {
        if(x % i == 0)
        {
            ans++;
            if(x / i != i) ans++;
        }
    }
    return ans;
}
int main()
{
    freopen("count.in","r",stdin);
    freopen("count.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    cout << solve(n) * solve(n - 1) << "\n";
    return 0;
}
```
## T2 - 三角形移动

### TooY0ung 的思路

首先，我们可以花费 $O(n)$ 的时间复杂度模拟出两个人走路的过程，这样可以得到 $a$ 和 $b$ 的坐标。

坐标转换成数字是很简单的，等差数列求和 + 列坐标就行了。

然后从 $a^2$ 走到 $b^2$，找一下规律，假设 $a^2$ 的坐标是 $(x_1,y_1)$， $b^2$ 的坐标是 $(x_2,y_2)$。

步数 = $|x_1 - x_2| + |y_1 - y_2|$。

关键的问题就是怎么算出他们的坐标。

其实一行一行加就行，复杂度是 $O(n)$ 的，或者如果你愿意挑战自己也可以写个二分。

### TooY0ung 的满分代码
```cpp
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
#include<stack>
#include<sstream>
#include<set>
#include<unordered_set>
#include<time.h>
#include<stdlib.h>
#include<unordered_map>
#include<random>
#include<iomanip>
#include<climits>
#define ll long long
#define ull unsigned long long
#define eps 1e-10
#define INF 1e9
#define delta 0.996
#define T 3000
#define pi acos(-1.0)
#define ld long double
#define vl vector<long long>
const ll mod1 = 1e9 + 7;
const ll mod2 = 998244353;
const ll mod3 = 1e9;
const int maxn = 2e5 + 10;
const int maxm = 5e5 + 10;
const int maxq = 5e5 + 10;
const int nn = maxn * 20;
const ll inf = 1e18L;
using namespace std;
typedef pair<int,int>Pii;
typedef pair<ll ,int>Pli;
typedef pair<int, pair<int, int>>Pi;
typedef pair<string, Pi>psp;
typedef pair<int, vector<int>>piv;
typedef pair<ll, ll>P;
int n;
string s, t;
struct d
{
    ll heng;
    ll zong;
};
d zb(ll num)
{
    ll a = 1;
    ll sum = 0;
    while(sum + a < num)
    {
        sum += a;
        a++;
    }
    ll b = num - sum;
    d ans;
    ans.heng = a;
    ans.zong = b;
    return ans;
}
int main()
{
    freopen("tri.in","r",stdin);
    freopen("tri.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> s >> t;
    // 聪聪
    ll a1 = 1, b1 = 1;
    for(char c : s)
    {
        if(c == 'L') b1--;
        if(c == 'R') b1++;
        if(c == 'U') a1--;
        if(c == 'D') a1++;
    }
    // 1 + 2 + ... + (a1 - 1) + b1
    ll num1 = a1 * (a1 - 1) / 2 + b1;
    ll a2 = 1, b2 = 1;
    for(char c : t)
    {
        if(c == 'L') b2--;
        if(c == 'R') b2++;
        if(c == 'U') a2--;
        if(c == 'D') a2++;
    }
    ll num2 = a2 * (a2 - 1) / 2 + b2;
    ll x = num1 * num1;
    ll y = num2 * num2;
    d xx = zb(x);
    d yy = zb(y);
    cout << abs(xx.heng - yy.heng) +
    abs(xx.zong - yy.zong) << "\n";
    return 0;
}
```
## T3 - 学知识

### TooY0ung 的思路

读完题会发现两个事情：

$1.$ $a_i <= 300$，这意味着，300轮之后，你的收获一定为 $0$，所以我们可以预处理出前 $300$ 轮的答案。

$2.$ 本质上询问的就是区间和，所以不妨我们可以做前缀和加速求区间和的速度。

那么不难想到答案的询问就是循环前缀和的右端点寻找满足的，这个过程显然可以二分加速从而保证代码不会超时。

整体来说这个题目思维难度是不高的。

### TooY0ung 的满分代码
```cpp
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
#include<stack>
#include<sstream>
#include<set>
#include<unordered_set>
#include<time.h>
#include<stdlib.h>
#include<unordered_map>
#include<random>
#include<iomanip>
#include<climits>
#define ll long long
#define ull unsigned long long
#define eps 1e-10
#define INF 1e9
#define delta 0.996
#define T 3000
#define pi acos(-1.0)
#define ld long double
#define vl vector<long long>
const ll mod1 = 1e9 + 7;
const ll mod2 = 998244353;
const ll mod3 = 1e9;
const int maxn = 2e5 + 10;
const int maxm = 5e5 + 10;
const int maxq = 5e5 + 10;
const int nn = maxn * 20;
const ll inf = 1e18L;
using namespace std;
typedef pair<int,int>Pii;
typedef pair<ll ,int>Pli;
typedef pair<int, pair<int, int>>Pi;
typedef pair<string, Pi>psp;
typedef pair<int, vector<int>>piv;
typedef pair<ll, ll>P;
ll a[100010], sum[300 * 100010], n, q;
int main()
{
    freopen("learn.in","r",stdin);
    freopen("learn.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    ll now = 1, zong = 300 * n;
    for(int day = 1; day <= zong; day++)
    {
        sum[day] = sum[day - 1] + a[now];
        if(a[now] > 0) a[now]--;
        now++;
        if(now == n + 1) now = 1;
    }
    while(q--)
    {
        ll x, t;
        cin >> x >> t;
        // sum[ans] - sum[x - 1] >= t
        // sum[ans] >= t + sum[x - 1]
        ll ans = lower_bound(sum + x, sum + zong + 1,
                             t + sum[x - 1]) - sum;
        if(sum[ans] - sum[x - 1] >= t)
            cout << ans << "\n";
        else cout << "-1\n";
    }
    return 0;
}
```
## T4 - 轮盘赌

### TooY0ung 的思路

测试点 1~3：会写快速幂就能拿到。

测试点 4~7：一共就 $20$ 轮，每一轮模拟一下是直接开枪好，还是转一下开枪好即可。时间复杂度 $O(20k)$。此处有一个小难点是需要提前预处理一个点向右有多少个连续的 $0$，当然能做到这个题这就不是难点了。

测试点 8~9：推一下就知道，对于开枪次数小于等于某个次数的时候，都是直接开枪更好，否则转一下更好，那么就很好模拟了，细节不表。

测试点 10~12：同理，这个也可以推出来，具体细节在正解中表达。

测试点 15：显然每次都要重新转一下，会写快速幂就可以拿到。

正解：

我们考虑对于已经连续开了 $i$ 枪的情况下，下一次是应该转还是不转？

如果转：下一枪的成功（成功就是发射失败）概率是 $\frac{n-one}{n}$，其中 $one$ 指的是序列里面 $1$ 的个数。

如果不转：下一枪的成功概率是 $\frac{sum_{i+1}}{sum_i}$，其中 $sum_i$ 指的是序列里面有多少个位置 $j$，包含其在内，向右至少有 $i$ 个 $0$。

处理 $sum_i$ 是一个小难点，不过也就红题难度啦。

那么，对于一个状态 $i$，可以走到哪里，以及走过去的概率，我们可以用 $to_i,g_i$ 来表示。

这时候，这就变成了一个有环的有向图了！

比如 $to_0=1,to_1=2,to_2=3,to_3=1$，那不就是从 $0$ 到 $1$，然后走 $2,3,1,2,3,1,...,$ 这样的序列吗？

问的是走过的所有的边的乘积是多少。

那这个就很简单了对不，我们从起点开始模拟，模拟出一个环，就可以直接把重复走这个环的过程“跳过”了。

预处理的时间复杂度是 $O(k)$ 的。

模拟的过程，时间复杂度是 $O(k+\log n)$ 的。

### TooY0ung 的满分代码
```cpp
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
#include<stack>
#include<sstream>
#include<set>
#include<time.h>
#include<stdlib.h>
#include<unordered_map>
#include<iomanip>
#include<bitset>
#include<cassert>
#define ll long long
#define ull unsigned long long
#define eps 1e-6
#define INF 1e9
#define delta 0.996
#define T 3000
#define pi acos(-1.0)
#define ld long double
const ll mod1 = 1e9 + 7;
const ll mod2 = 998244353;
const int maxn = 1e5 + 10;
const ll inf=1e18L;
using namespace std;
typedef pair<int,int> Pii;
typedef pair<ll,int> Pli;
typedef pair<ll,ll>P;
typedef pair<int, pair<int, int>>Pipii;
ll k, n, one;
string s;
// 1 2 3 4
// 1 2 3 4 1 2 3 4
ll R[maxn * 2], sum[maxn]; //算i右边有多少个0
int to[maxn]; //表示当前连续开了i次，下一次去哪
ll gg[maxn]; //表示当前开了i次，下一次成功率是多少
ll vis[maxn]; //曾经第几轮来过这里
ll f[maxn]; // 曾经来这里的时候的概率
ll pw(ll a, ll b) // a^b % c
{
    ll ans = 1;
    while(b != 0)
    {
        if(b % 2 == 1)
        {
            ans = (ans * a) % mod2;
        }
        a = (a * a) % mod2;
        b /= 2;
    }
    return ans;
}
int main()
{
    freopen("rou.in","r",stdin);
    freopen("rou.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> k >> n;
    cin >> s;
    s = s + s;
    for(int i = 2 * n - 1; i >= 0; i--)
    {
        if(s[i] == '0') R[i] = R[i + 1] + 1;
        else
        {
            R[i] = 0;
            one++;
        }
    }
    one /= 2;
    for(int i = 1; i <= n; i++)
        sum[R[i]]++; //恰好i个0的
    for (int i = n; i >= 1; i--)
        sum[i] += sum[i + 1]; //至少i个0的
    pair<ll,ll> g1 = {n - one, n}, g2; //这是直接开的概率,g2是另一个
    to[0] = 1;
    gg[0] = (n - one) * pw(n, mod2 - 2) % mod2;
    for(int i = 1; i < n; i++)
    {
        //g2 跟 sum[i + 1] / sum[i] 绑定
        if (sum[i] >= 1)
            g2 = {sum[i + 1], sum[i]};
        else g2 = {0, 0};
        // 转动的概率 <= 不转的概率
        // g2.first/g2.second <= g1.first/g1.second;
        if(g2.first * g1.second <= g1.first * g2.second)
        {
            to[i] = 1;
            gg[i] =(n - one) * pw(n, mod2 - 2) % mod2;
        }
        else
        {
            to[i] = i + 1;
            gg[i] = sum[i + 1] * pw(sum[i],mod2 - 2) % mod2;
        }
    }
    //开始模拟
    int now = 0;
    ll F = 1;
    for (ll tian = 1; tian <= k; tian++)
    {
        //先模拟一天
        F = F * gg[now] % mod2;
        now = to[now];
        if(vis[now] != 0) //曾经来过此处
        {
            ll tt = F * pw(f[now], mod2 - 2) % mod2; //这是这一圈的概率
            ll zhouqi = tian - vis[now]; //这是转一圈需要的次数
            ll quan = (k - tian) / zhouqi; //还能转这么多圈
            F = F * pw(tt, quan) % mod2;
            tian += zhouqi * quan;
        }
        else vis[now] = tian, f[now] = F;
    }
    cout << F << "\n";
    return 0;
}

```