2020牛客寒假算法基础集训营1 考点算法教程与例题集合

期望与概率

尺取法

约数个数

其实这题没那么难优化什么的

$[1,n]$里约数有$i$的个数是$\lfloor\frac ni\rfloor$

所以$ans=\sum_{i=1}^n\lfloor\frac ni\rfloor$然后我们打表发现

有很多$\lfloor\frac ni\rfloor$都是一样的 对于这些一样的数我们每次算一次 似乎很浪费时间

所以我们每次 $i$ 跳到$\lfloor\frac nj\rfloor=\lfloor\frac ni\rfloor+1$这样的 $j$ 上 对于中间一样的数一次性算掉

这样的复杂度又是多少呢?打表测试一下就好了 复杂度$O(2\sqrt n)$//其实这道题数据范围可以出到$10^{14}$的 手动滑稽

搜索

DP

二分答案

欧拉降幂

降幂公式:

$$ a^b \equiv \begin{cases}a^{b\%\varphi(p)} & gcd(a,p)=1\\a^b& gcd(a,p)\neq1,b<\varphi(p)\\a^{b\%\varphi(p)+\varphi(p)}&gcd(a,p)\neq1,b\geq\varphi(p)\end{cases} $$

矩阵快速幂

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+7;
int mod;
struct Matix{
    static const int _size=2;
    ll m[50][50];
    Matix(){
        memset(m, 0, sizeof(m));
    }
    void InitC(ll a=1){
        for(int i=0;i<_size;++i)m[i][i]=a;
    }
    Matix operator*(const Matix &m2){
        Matix t;
        for (int i = 0; i < _size; ++i)
            for (int j = 0; j < _size; ++j)
                for (int k = 0; k < _size; ++k)
                    t.m[i][j] = (t.m[i][j] + m[i][k] * m2.m[k][j]) % mod;
        return t;
    };
    ll* const operator [] (const int i){
        return m[i];
    }
    Matix operator^(int k) {
         Matix x = *this, ans;
         ans.InitC();        //初始化对角矩阵
         while (k) {
             if (k&1)
                 ans = ans * x;
            x = x * x;
            k >>= 1;
           }
           return ans;
      }
    Matix operator^(char *s){        //10进制快速幂
        Matix g = *this,res;
        res.InitC();
        int len=strlen(s);
        for(int i=len-1;i>=0;--i){
            if(s[i]!='0')res=res*(g^(s[i]-'0'));
            g=g^10;
        }
        return res;
    }
}g, u;
ll x[10];
char n[maxn];
int main(){
    ll a,b,ans=0;
    scanf("%lld%lld%lld%lld",&x[0],&x[1],&a,&b);
    scanf("%s%lld",n,&mod);
    g[0][0]=0,g[0][1]=1,g[1][0]=b,g[1][1]=a;
    u=g^n;      //求g的n次方
    for(int i=0;i<2;i++)ans=(ans+x[i]*u[0][i])%mod;
    printf("%lld\n",ans);
}
Last modification:April 17th, 2020 at 01:30 pm
如果觉得我的文章对你有用,请随意赞赏