danihao123

搜索

音乐播放器

RSS

RSS Link

计数器

29165

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

2017年9月25日 12:56 | Comments(0) | Category:大坑 | Tags:

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

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

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

\[\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]沙拉公主的困惑

2016年10月11日 21:59 | Comments(0) | Category:题解 | Tags:

这个题啊……亦可赛艇!

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

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

并且……[tex]n-m[/tex]可能非常大,所以说除去[tex]m![/tex]那块要用逆元做。

(顺便说下阶乘也要递推)

代码:

/**************************************************************
    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]墨墨的等式

2016年9月11日 15:16 | Comments(0) | Category:题解 | Tags:

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

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

取模后,[tex]B\in Z_p[/tex],所以说只要对于[tex]Z_p[/tex]中的每个数找出最小的一组合法解即能推出其他解(所以说,剩余系越少效率越高,这也就要求取的[tex]a_i[/tex]要小)。不过这个最小的一组合法解怎么找?

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

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

注意忽略[tex]a_i=0[/tex]的情况(相当于不存在)。

代码:

/**************************************************************
    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;
}


[BZOJ 2190]仪仗队

2016年9月04日 17:46 | Comments(0) | Category:题解 | Tags:

这个题啊……有规律可循。

我们可以发现,关于答案[tex]a[/tex]有如下规律:

[tex]a+1=2\mul (\Sigma_{i=2}^{n-1}\varphi(i)+2)[/tex]

然后筛法求欧拉函数即可(我听说神犇们都用了杜教筛哎)

代码:

/**************************************************************
    Problem: 2190
    User: danihao123
    Language: C++
    Result: Accepted
    Time:28 ms
    Memory:976 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=40005;
#define CUS_REP(i,a,b) for(i=(a);i<=(b);i++)
 
int phi[maxn];
int n;
void sieve(){
    register int i,j;
    phi[1]=1;
    CUS_REP(i,2,n)
        if(!phi[i])
            for(j=i;j<=n;j+=i){
                if(!phi[j])
                    phi[j]=j;
                phi[j]=phi[j]/i*(i-1);
            }
}
 
int main(){
    register int i,ans=2;
    scanf("%d",&n);
    sieve();
    /*
    #ifdef DEBUG
    CUS_REP(i,1,n)
        printf("%d\n",phi[i]);
    #endif
    */
    CUS_REP(i,2,n-1)
        ans+=phi[i];
    printf("%d\n",ans*2-1);
    return 0;
}


[洛谷 P2312]解方程

2016年8月21日 21:32 | Comments(0) | Category:题解 | Tags:

最凶残的NOIP题。

首先我们可能会想到暴力枚举验证(枚举[tex][1,m][/tex]带入),然后我们很快就会想到用几个素数取模乱搞。然后嘛……

对于我们用到的取模数[tex]k[/tex],带入任意[tex]x[/tex],都有[tex]x^{a}\ mod\ k \in Z_{k} (a \in N^{0})[/tex](废话),所以说实际上我们枚举带入的是[tex][1,k)[/tex]。

这个题可以不开高精,因为可以一边读入一边取模

代码:

#include <cstdio>
#include <cctype>
#include <vector>
#include <algorithm>
using namespace std;

const int maxn=105,maxm=1000005;
const int P1=3079,P2=3083,P3=1000000207;

int X1[maxn],X2[maxn],X3[maxn];
bool Ac_1[P1],Ac_2[P2];

typedef long long ll;

inline ll mul_mod(ll a,ll b,ll Mod){
    return ((a%Mod)*(b%Mod))%Mod;
}

inline int readint(){
    register int ans=0;
    register char c=getchar();
    while(!isdigit(c)){
        c=getchar();
    }
    while(isdigit(c)){
        ans=ans*10+c-'0';
        c=getchar();
    }
    return ans;
}
inline void read_mod(int& a,int& b,int& c){
    a=b=c=0;
    bool flag=false;
    register char cr=getchar();
    while(!isdigit(cr)){
        if(cr=='-')
            flag=true;
        cr=getchar();
    }
    while(isdigit(cr)){
        a=(mul_mod(10,a,P1)+cr-'0')%P1;
        b=(mul_mod(10,b,P2)+cr-'0')%P2;
        c=(mul_mod(10,c,P3)+cr-'0')%P3;
        cr=getchar();
    }
    if(flag){
        a=(P1-a)%P1;
        b=(P2-b)%P2;
        c=(P3-c)%P3;
    }
}

int n;
bool check(int* A,int x,int Mod){
    int now=0;
    register int i;
    for(i=n;i>=0;i--){
        now=(mul_mod(now,x,Mod)+A[i])%Mod;
    }
    return now==0;
}

vector<int> AnsList;
int main(){
    int m;
    register int i,ans_count=0;
    n=readint();
    m=readint();
    for(i=0;i<=n;i++)
        read_mod(X1[i],X2[i],X3[i]);
    for(i=1;i<P1;i++)
        Ac_1[i]=check(X1,i,P1);
    for(i=1;i<P2;i++)
        Ac_2[i]=check(X2,i,P2);
    for(i=1;i<=m;i++){
        if(Ac_1[i%P1] && Ac_2[i%P2] && check(X3,i,P3)){
            ans_count++;
            AnsList.push_back(i);
        }
    }
    printf("%d\n",ans_count);
    for(i=0;i<AnsList.size();i++){
        printf("%d\n",AnsList[i]);
    }
    return 0;
}

[BZOJ 1441]Min

2016年8月17日 16:01 | Comments(0) | Category:题解 | Tags:

这个问题看似无从下手。

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

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

代码:

/**************************************************************
    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

2016年8月16日 13:57 | Comments(0) | Category:题解 | Tags:

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

(大胆猜想,不用证明

代码:

#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]最大公约数和最小公倍数问题

2016年8月03日 18:34 | Comments(0) | Category:题解 | Tags:

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

应注意[tex]P*Q=x*y[/tex],然而[tex]P[/tex]和[tex]Q[/tex]都可表示为[tex]x[/tex]的乘积,问题就好思考多了。答案就是[tex]y/x[/tex]的质因子的子集数(同一种质因子不能同时分配到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 1607]轻拍牛头

2016年5月15日 13:43 | Comments(0) | Category:题解 | Tags:

噫……筛法

然而……人傻自带大常数

代码:

[BZOJ 2296]随机种子

2016年4月02日 22:23 | Comments(1) | Category:题解 | Tags:

现在才明白,我数论其实不好……

这题也不怎么难,需要一点灵感构造

代码: