「kuangbin带你飞」专题十四 数论基础

layout: post
title: 「kuangbin带你飞」专题十四 数论基础
author: "luowentaoaa"
catalog: true
tags:
mathjax: true
- kuangbin
- 数论

传送门

A - Bi-shoe and Phi-shoe(欧拉函数的性质)

题意

给出一些数字，对于每个数字找到一个欧拉函数值大于等于这个数的数，求找到的所有数的最小和。

思路

考察了欧拉函数的简单性质，即满足欧拉函数(k)>=N的最小数为N+1之后的第一个素数

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=2e6+1000;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
bool check[maxn];
int phi[maxn];
int prime[maxn];
int tot;
vector<int>ppp;
void phi_table(int n){
    phi[1]=1;
    tot=0;
    for(int i=2;i<=n;i++){
        if(!check[i]){prime[tot++]=i;phi[i]=i-1;ppp.push_back(i);}
        for(int j=0;j<tot;j++){
            if(i*prime[j]>n)break;
            check[i*prime[j]]=true;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    phi_table(2000000);
    int t;
    int cnt=1;
    cin>>t;
    while(t--){
        int n;cin>>n;
        vector<int>ve;
        ll ans=0;
        for(int i=1;i<=n;i++){
            int a;
            cin>>a;
            ans+=ppp[lower_bound(ppp.begin(),ppp.end(),a+1)-ppp.begin()];
        }
        cout<<"Case "<<cnt++<<": "<<ans<<" Xukha"<<endl;
    }
    return 0;
}

C - Aladdin and the Flying Carpet（唯一分解定理）

题意

给一对数字 a，b ，a是一个长方形的面积，问有多少种整数的边的组合可以组成面积为a的长方形，要求最短的边不得小于b

思路

唯一分解定理

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+1000;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
bool check[maxn];
int phi[maxn];
int prime[maxn];
int tot;
void phi_table(int n){
    phi[1]=1;
    tot=0;
    for(int i=2;i<=n;i++){
        if(!check[i]){prime[tot++]=i;phi[i]=i-1;}
        for(int j=0;j<tot;j++){
            if(i*prime[j]>n)break;
            check[i*prime[j]]=true;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}
ll getnum(ll n){
    ll ans=1,num=0;
    for(int i=0;i<tot&&prime[i]*prime[i]<=n;i++){
        if(n%prime[i]==0){
            num=0;
            while(n%prime[i]==0){
                n/=prime[i];
                num++;
            }
            ans*=(num+1);
        }
    }
    if(n>1)ans*=2;
    return ans;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    int cnt=1;
    cin>>t;
    phi_table(1000000+50);
    while(t--){
        ll a,b;
        cin>>a>>b;
        if(a<=b*b){
            cout<<"Case "<<cnt++<<": ";
            cout<<0<<endl;
            continue;
        }
        ll ans=getnum(a)/2;
        for(ll i=1;i<b;i++){
            if(a%i==0)ans--;
        }
        cout<<"Case "<<cnt++<<": ";
        cout<<ans<<endl;
    }
    return 0;
}

D - Sigma Function （平方数和平方数×2的约数和是奇数 ）

题意

求1-n中的因子和为偶数的个数是多少

思路

平方数和平方数*2的约数和是奇数

而且-----平方数*2的个数就等于sqrt（n/2）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+1000;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    int cnt=1;
    cin>>t;
    while(t--){
        ll ans;
        cin>>ans;
        ans-=floor(sqrt(ans))+floor(sqrt(ans/2));
        cout<<"Case "<<cnt++<<": ";
        cout<<ans<<endl;
    }
    return 0;
}

E - Leading and Trailing(求 n^k 前3项和后3项)

思路

后三项不需要想就知道是快速幂了

但是前三项需要推一下

我们知道任意数可以转化成 X = 10^( x + y ) (x为整数，y为小数)

其中 10^x 来控制的是源数字 10 100.。。这样的东西，而具体这个数字等于多少，全靠10^y ，

那么 我们就可知道 10^y 就是我们要求的前n个数字还不会炸 long long (用double的话末尾消去，很适合)

这样我们就能保证前7位可知， 如果要前三位 只需要 10^(y) * 100 就好了。

由于这道题数据卡的不是太死。。限时 2s ，那么不用快速幂去搞前三位。。似乎没事。

fmod 是一个特殊函数 fmod(a,b) (a , b 为 浮点型) 得出的结果是 a / b 得出的结果的小数。。

距离 fmod( 4, 3 ) 结果为 0.3333333 ，那么我们这样 fmod( x , 1 ) 就是默认取他的小数点位

那么 对于 X^k = 10^x * 10^y

x + y = k * lg X ,那么 y = fmod( k*lg X, 1.0 )

然后再*100就是前三位了。。。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+1000;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int pow_mod(int x,int n,int mod){
    int res=1;
    while(n){
        if(n&1)res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res;
}

int main()
{
    /*std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);*/
    int t;
    int cnt=1;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        int ans1=pow(10.0,fmod(k*log10(n*1.0),1))*100;
        int ans2=pow_mod(n%1000,k,1000);
        printf("Case %d: %03d %03d\n",cnt++,ans1,ans2);
    }
    return 0;
}

F - Goldbach`s Conjecture (线性筛)

题意

T组询问，每组询问是一个偶数n
验证哥德巴赫猜想
回答n=a+b
且a，b(a<=b)是质数的方案个数

思路

注意不要被卡内存就行

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e7+10;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
bool check[maxn];
int prime[700000];
int tot;
void getprime(){
    tot=0;
    for(int i=2;i<maxn;i++){
        if(!check[i]){
            prime[tot++]=i;
        }
        for(int j=0;j<tot;j++){
            if(i*prime[j]>=maxn)break;
            check[i*prime[j]]=true;
            if(i%prime[j]==0)break;
        }
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    int cnt=1;
    cin>>t;
    getprime();
    while(t--){
        int n;
        cin>>n;
        int ans=0;
        for(int i=0;i<tot&&prime[i]*2<=n;i++){
            if(!check[n-prime[i]])ans++;
        }
        cout<<"Case "<<cnt++<<": ";
        cout<<ans<<endl;
    }
    return 0;
}

G - Harmonic Number (II)（整除分块）

题意

求f(n)=n/1+n/2.....n/n,其中n/i保留整数;

思路

直接套莫比乌斯反演的整除分块

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e7+10;
const ll inf=0x3f3f3f3f3f3f3f3fLL;

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    int cnt=1;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        ll ans=0;
        for(ll l=1,r;l<=n;l=r+1){
            r=n/(n/l);
            ans+=(r-l+1)*(n/l);
        }
        cout<<"Case "<<cnt++<<": ";
        cout<<ans<<endl;
    }
    return 0;
}

H - Pairs Forming LCM (唯一分解定理)

题意

求有多少组 （ i，j ）
使 lcm(i, j) = n and (i ≤ j).
(1 ≤ n ≤ 10^14)

思路

图片来源

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e7+10;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
bool check[maxn];
int prime[1000000];
int tot;
void getprime(){
    tot=0;
    for(int i=2;i<maxn;i++){
        if(!check[i]){
            prime[tot++]=i;
        }
        for(int j=0;j<tot;j++){
            if(i*prime[j]>=maxn)break;
            check[i*prime[j]]=true;
            if(i%prime[j]==0)break;
        }
    }
}
ll getnum(ll n){
    ll ans,sum;
    ans=0;
    sum=1;
    for(int i=0;i<tot&&prime[i]*prime[i]<=n;i++){
        if(n%prime[i]==0){
            ans=0;
            while(n%prime[i]==0){
                n/=prime[i];
                ans++;
            }
            sum*=(2*ans+1);
        }
    }
    if(n>1)sum*=3;
    return sum;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    int cnt=1;
    cin>>t;
    getprime();
    while(t--){
        ll n;
        cin>>n;
        cout<<"Case "<<cnt++<<": ";
        cout<<getnum(n)/2+1<<endl;
    }
    return 0;
}

I - Harmonic Number (欧拉常数 /稀疏打表求调和级数)

题意

t组数据，每组一个n 求 1+1/2+1/3+1/4 ......+1/n的和

思路

直接100个一组打表求前1e7项

或者直接套公式

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
double num[maxn];
void init(){
    num[0]=0;
    num[1]=1.0;
    double ans=1.0;
    for(int i=2;i<=100000000;i++){
        ans+=1.0/(i*1.0);
        if(i%100==0)num[i/100]=ans;
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    int cnt=1;
    cin>>t;
    init();
    while(t--){
        int n;
        cin>>n;
        int k=n/100;
        double ans=num[k];
        for(int i=k*100+1;i<=n;i++)ans+=1.0/(i*1.0);
        cout<<"Case "<<cnt++<<": ";
        cout<<fixed<<setprecision(10);
        cout<<ans<<endl;
    }
    return 0;
}

「kuangbin带你飞」专题十四 数论基础

原文：https://www.cnblogs.com/luowentao/p/10386517.html