danihao123's Blog

[坑]狄利克雷卷积和反演

开个坑，记录一些和反演以及狄利克雷卷积的东西。

首先积性函数、狄利克雷卷积等基本概念不写了，就讲讲性质吧。

有几个一定要记住的东西：

$\mu \ast 1 = e$

$\varphi \ast 1 = id$

$\mu \ast id = \varphi$

这几个在推式子的过程中都有很大的作用，务必要记住。

所谓莫比乌斯反演，其实就是：

$F = f \ast 1\Leftrightarrow f = F \ast \mu$

（谜之音：其实很多所谓“反演题”都没用到这俩性质啊……）

关于莫比乌斯函数本身，还有一个好康的性质：

$(\mu\ast 1)(k) = \sum_{i = 0}^k (-1)^i C_k^i$

继续阅读

[BZOJ 2186]沙拉公主的困惑

这个题啊……亦可赛艇！

答案是 $\varphi(m!)*n!/m!$ 。原因很简单，把 $[1,n!]$ 分成长度为 $m!$ 的若干段，除去第一段外每一段中与 $m!$ 互质的数 $k$ 肯定满足 $(k\bmod m!,m!)=1$ （否则， $k$ 和 $m!$ 就会有大于一的公因子了)。所以说每一段内与 $m!$ 互质的数都有 $\varphi(m!)$ 个。

麻烦好像就在于求一个阶乘的欧拉函数。考虑一个新乘上的数能给答案带来的贡献——如果这个数是合数，它的所有因子在前面都有了，只能把他自己贡献出来；如果这个数是质数（假设为 $p$ ），出了贡献自己以外还会贡献一个 $(1-1/p)$ ，最后乘起来就是贡献了 $p-1$ 。筛一遍素数再递推一下就好辣~

并且…… $n-m$ 可能非常大，所以说除去 $m!$ 那块要用逆元做。

（顺便说下阶乘也要递推）

代码：

/**************************************************************
    Problem: 2186
    User: danihao123
    Language: C++
    Result: Accepted
    Time:9408 ms
    Memory:166836 kb
****************************************************************/
  
#include <cstdio>
#include <cmath>
typedef unsigned long long ull;
const int maxn=10000000;
ull R;
bool vis[maxn+5];
inline void sievePrime(){
    register int i,j,m=sqrt(maxn+0.5);
    for(i=2;i<=m;i++)
        if(!vis[i])
            for(j=i*i;j<=maxn;j+=i)
                vis[j]=true;
}
ull fac[maxn+5];
inline void sieveFac(){
    register int i;
    fac[0]=1%R;
    for(i=1;i<=maxn;i++)
        fac[i]=(fac[i-1]*(i%R))%R;
}
ull phifac[maxn+5];
inline void sievePhiFac(){
    register int i;
    phifac[1]=1%R;
    for(i=2;i<=maxn;i++){
        if(vis[i])
            phifac[i]=(phifac[i-1]*(i%R))%R;
        else
            phifac[i]=(phifac[i-1]*((i%R-1%R+R)%R))%R;
    }
}
void exgcd(ull a,ull b,ull& d,ull& x,ull& y){
    if(!b){
        d=a;
        x=1;
        y=0;
    }else{
        exgcd(b,a%b,d,y,x);
        y-=x*(a/b);
    }
}
ull inv(ull a){
    ull d,x,y;
    exgcd(a,R,d,x,y);
    return (x+R)%R;
}
int main(){
    int T;
    int n,m;
    scanf("%d%llu",&T,&R);
    sievePrime();
    sieveFac();
    sievePhiFac();
    while(T--){
        scanf("%d%d",&n,&m);
        printf("%llu\n",(phifac[m]*((fac[n]*inv(fac[m]))%R))%R);
    }
    return 0;
}

[BZOJ 2118]墨墨的等式

论如何把数论乱搞和图论乱搞出在一起……

这个题由于要求 $x\ge 0$ ，所以不能gcd乱搞。我们可以先取 $\{a_n\}$ 的最小值 $p$ （忽略为0的情况，为啥取最小值待会再说），对方程两边模 $p$ 。然后对于任何能使某个同余方程成立的 $\{x_n\}$ ，将其中所有 $x_i$ 同时加任意个 $p$ ，同余方程都成立。

取模后， $B\in Z_p$ ，所以说只要对于 $Z_p$ 中的每个数找出最小的一组合法解即能推出其他解（所以说，剩余系越少效率越高，这也就要求取的 $a_i$ 要小）。不过这个最小的一组合法解怎么找？

我们先找出任意一个合法 $B$ （比如说0吧），然后尝试加上 $a_i$ ，就可以推出其他 $B\in Z_p$ 的最小解。这个应用当然是需要最短路辣。

求出来的最短路，表示的是取最小解时的 $B$ 。这样的话就可以推出某个前缀区间中合法 $B$ 的个数（能加多少 $p$ ，就有多少个，注意不要忽略加0个的情况），并且答案符合区间减法，最后做差分即可。

注意忽略 $a_i=0$ 的情况（相当于不存在）。

代码：

/**************************************************************
    Problem: 2118
    User: danihao123
    Language: C++
    Result: Accepted
    Time:1952 ms
    Memory:5508 kb
****************************************************************/
  
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#ifdef DEBUG
#include <cassert>
#endif
using namespace std;
typedef long long ll;
const int maxn=15;
const ll INF=0x7f7f7f7f7f7f7f7f;
ll A[maxn];
bool inQueue[500005];
ll d[500005];
int n;
ll minv;
inline void SPFA(){
    register int i,u,to;
    queue<int> Q;
    memset(d,0x7f,sizeof(d));
    d[0]=0;
    Q.push(0);
    inQueue[0]=true;
    #ifdef DEBUG
    assert(d[1]==INF);
    #endif
    while(!Q.empty()){
        u=Q.front();
        Q.pop();
        inQueue[u]=false;
        for(i=1;i<=n;i++){
            to=(u+A[i])%minv;
            if(d[u]<INF && d[u]+A[i]<d[to]){
                d[to]=d[u]+A[i];
                if(!inQueue[to]){
                    Q.push(to);
                    inQueue[to]=true;
                }
            }
        }
    }
}
  
inline ll Calc(ll x){
    register ll ans=0;
    register int i=0;
    for(i=0;i<minv;i++)
        if(d[i]<=x)
            ans+=(x-d[i])/minv+1;
    return ans;
}
  
int main(){
    ll l,r;
    register int i;
    scanf("%d%lld%lld",&n,&l,&r);
    minv=0x7fffffff;
    for(i=1;i<=n;i++){
        scanf("%d",&A[i]);
        if(!A[i]){
            i--;
            n--;
            continue;
        }
        minv=min(minv,A[i]);
    }
    SPFA();
    printf("%lld\n",Calc(r)-Calc(l-1));
    return 0;
}
﻿

[CF 711D]Directed Roads

这个题啊……其实不难。

首先你注意，他告诉你你可以把边弄反。

其次注意，这个图不一定就有一个环。

然后每个环的取反法有 $2^x$ 种（假设环中有 $x$ 条边），但是空集不行，全集也不行，因此每个环爆掉的方案有 $2^x-2$ 种。然后环之外的边随便弄，乘法原理乱搞即可。

然后你是不是感觉这个题似曾相识？是的似乎这个题就是NOIP D1T2的翻版。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=200001;
const ll MOD=1000000007;
int G[maxn];
int in[maxn];
bool vis[maxn];
int n;
inline bool jianz(){
    register int i;
    bool ans=false;
    for(i=1;i<=n;i++){
        if(!vis[i] && !in[i]){
            ans=true;
            in[G[i]]--;
            vis[i]=true;
            G[i]=0;
        }
    }
    return ans;
}
ll dfs(int x,int y){
    if(x==y && vis[x]){
        return 0;
    }else{
        vis[x]=true;
        return dfs(G[x],y)+1;
    }
}
ll pow_mod(ll a,ll b){
    if(!b){
        return 1;
    }else{
        ll ans=pow_mod(a,b/2);
        ans=ans*ans%MOD;
        if(1&b){
            ans=(ans*(a%MOD))%MOD;
        }
        return ans;
    }
}
inline ll solve(){
    register int i;
    register ll Huan,temp=0,ans=1;
    while(jianz());
    for(i=1;i<=n;i++)
        if(!vis[i]){
            Huan=dfs(i,i);
            temp+=Huan;
            ans=(ans*(pow_mod(2,Huan)+MOD-2))%MOD;
        }
    ans=(ans*pow_mod(2,n-temp))%MOD;
    return ans;
}
int main(){
    register int i;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&G[i]);
        in[G[i]]++;
    }
    printf("%I64d\n",solve());
    return 0;
}

[CF 707C]Pythagorean Triples

很好的数学题啊……

一看就应该想起来构造，对于 $n$ 为奇数的情况，我们可以假设 $n$ 为最小数。由此，可以构造出来 $(n,(n^{2}-1)/2,(n^{2}-1)/2+1)$ 一组勾股数（具体证明自己证去）。

$n$ 为偶数时呢？化成奇数做？不好，因为这样会出现对于 $n^{a} (a>1)$ 一类数会无能为力。偶数也可构造： $(n,(n/2)^{2}-1,(n/2)^{2}+1)$ 。

然后做就行了……

#include <iostream>
using namespace std;
int main(){
    long long n,temp;
    cin>>n;
    if(n<=2){
        cout<<-1<<endl;
        return 0;
    }
    if(1&n){
        temp=n*n-1;
        temp/=2;
        cout<<temp<<' '<<(temp+1)<<endl;
    }else{
        temp=n/2;
        cout<<temp*temp+1<<' '<<temp*temp-1<<endl;
    }
    return 0;
}

[BZOJ 1441]Min

这个问题看似无从下手。

我们可以先取 $n=2$ ，然后你就发现你似乎要解 $A_{1}X_{1}+A_{2}X_{2}>0$ ，而且还要求 $S$ 最小？你想到了什么？扩展欧几里得？对头！

由扩欧推广可得答案就是所有数的最大公约数。

代码：

/**************************************************************
    Problem: 1441
    User: danihao123
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:820 kb
****************************************************************/
  
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}
int main(){
    register int ans,i;
    int n,temp;
    scanf("%d",&n);
    scanf("%d",&temp);
    ans=abs(temp);
    for(i=2;i<=n;i++){
        scanf("%d",&temp);
        ans=gcd(ans,abs(temp));
    }
    printf("%d\n",ans);
    return 0;
}

[CF 371B]Fox Dividing Cheese

狐狸的三种操作的实质是除二，除三，除五。由此我们可以猜想在最优策略下，两块蛋糕最后的重量应该是 $gcd(a,b)$ 。然后试除即可。

（大胆猜想~~，不用证明~~）

代码：

#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int a,int b){
    if(!b)
        return a;
    else
        return gcd(b,a%b);
}
static int P[3]={2,3,5};
inline int min_fj(int source,int direction){
    register int i,ans=0;
    source/=direction;
    if(source==1)
        return 0;
    for(i=2;i>=0;i--){
        while(source%P[i]==0){
            source/=P[i];
            ans++;
        }
    }
    if(source==1)
        return ans;
    else
        return -1;
}
int main(){
    register int direction,t1,t2;
    int a,b;
    cin>>a>>b;
    if(a==b){
        cout<<0<<endl;
        return 0;
    }
    direction=gcd(a,b);
    t1=min_fj(a,direction);
    if(t1==-1){
        cout<<-1<<endl;
        return 0;
    }
    t2=min_fj(b,direction);
    if(t2==-1){
        cout<<-1<<endl;
        return 0;
    }
    cout<<t1+t2<<endl;
    return 0;
}

[CodeVS 1012]最大公约数和最小公倍数问题

很经典的问题了吧……然而现在才A……

应注意 $P*Q=x*y$ ，然而 $P$ 和 $Q$ 都可表示为 $x$ 的乘积，问题就好思考多了。答案就是 $y/x$ 的质因子的子集数（同一种质因子不能同时分配到P与Q中，否则gcd(P,Q)会不等于x）。

注意有可能无解！

代码：

#include <iostream>
using namespace std;
inline int fj(int x){
    register int i,ans=0;
    for(i=2;i<=x && x>1;i++)
        if(!(x%i)){
            ans++;
            while(!(x%i))
                x/=i;
        }
    return ans;
}
int main(){
    int a,b;
    register int ans;
    cin>>a>>b;
    if(b%a)
        ans=0;
    else
        ans=a==1?1:1<<fj(b/a);
    cout<<ans<<endl;
    return 0;
}

[BZOJ 3713]Iloczyn

这题应该注意到，斐波纳契函数增长速度很快， $10^9$ 以下的斐波纳契函数值很少，所以可以打表。这样，问题就迎刃而解了。

代码：

/**************************************************************
    Problem: 3713
    User: danihao123
    Language: C++
    Result: Accepted
    Time:20 ms
    Memory:828 kb
****************************************************************/
  
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int fib[46]={0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170};
bool check(int n){
    int m=sqrt(0.5+n);
    if(binary_search(fib,fib+46,n))
        return true;
    register int i;
    for(i=2;i<=m;i++){
        if(!(n%i) && binary_search(fib,fib+46,i)){
            if(binary_search(fib,fib+46,n/i))
                return true;
        }
    }
    return false;
}
int main(){
    int T,n;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        if(check(n))
            puts("TAK");
        else
            puts("NIE");
    }
    return 0;
}

[BZOJ 1607]轻拍牛头

噫……筛法

然而……人傻自带大常数

代码：