brz的函数

brz的函数

https://ac.nowcoder.com/acm/contest/8282/D

推公式题。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e4+7;

ll ans[maxn], mu_fac_sum[maxn];
bool vis[maxn];
int prime[maxn];
int Mob[maxn];
void init(){
     int cnt = 0;
     vis[1] = 1;
     Mob[1] = 1;
     for(int i = 2; i <= maxn; i++){
        if(!vis[i])
            prime[cnt++] = i, Mob[i] = - 1;
        for(int j = 0; j < cnt && 1LL * prime[j] * i <= maxn; j++){
            vis[prime[j] * i] = 1;
            Mob[i * prime[j]] = (i % prime[j] ? -Mob[i]: 0);
            if(i % prime[j] == 0)
                break;
        }
    }

    ans[1] = 1;
    mu_fac_sum[1] = 1;
    for(int i = 2; i < maxn; i++)
    {
        ans[i] = ans[i-1];
        for(int j = 1; j * j <= i; j++){
            if(i % j == 0)
            {
                ans[i] += Mob[j]*(Mob[i]*Mob[i] + 2*Mob[i]*mu_fac_sum[j]);
                mu_fac_sum[j] += Mob[i];

                if(j * j != i)
                {
                    ans[i] += Mob[i/j]*(Mob[i]*Mob[i] + 2*Mob[i]*mu_fac_sum[i/j]);
                    mu_fac_sum[i/j] += Mob[i];
                }
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    init();
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        cout << ans[n] << endl;
    }
}

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
2022-12-28 02:13
门头沟学院_2024
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-22 16:33
重庆工商大学_2024
点赞 评论 收藏
转发
2 收藏 评论
分享

全站热榜

正在热议