[坑]狄利克雷卷积和反演
开个坑，记录一些和反演以及狄利克雷卷积的东西。
首先积性函数、狄利克雷卷积等基本概念不写了，就讲讲性质吧。
有几个一定要记住的东西：
\[\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]沙拉公主的困惑
这个题啊……亦可赛艇！
答案是[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]墨墨的等式
论如何把数论乱搞和图论乱搞出在一起……
这个题由于要求[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;
}
[CF 711D]Directed Roads
这个题啊……其实不难。
首先你注意，他告诉你你可以把边弄反。
其次注意，这个图不一定就有一个环。
然后每个环的取反法有[tex]2^x[/tex]种（假设环中有[tex]x[/tex]条边），但是空集不行，全集也不行，因此每个环爆掉的方案有[tex]2^x-2[/tex]种。然后环之外的边随便弄，乘法原理乱搞即可。
然后你是不是感觉这个题似曾相识？是的似乎这个题就是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
很好的数学题啊……
一看就应该想起来构造，对于[tex]n[/tex]为奇数的情况，我们可以假设[tex]n[/tex]为最小数。由此，可以构造出来[tex](n,(n^{2}-1)/2,(n^{2}-1)/2+1)[/tex]一组勾股数（具体证明自己证去）。
[tex]n[/tex]为偶数时呢？化成奇数做？不好，因为这样会出现对于[tex]n^{a} (a>1)[/tex]一类数会无能为力。偶数也可构造：[tex](n,(n/2)^{2}-1,(n/2)^{2}+1)[/tex]。
然后做就行了……
#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
这个问题看似无从下手。
我们可以先取[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
狐狸的三种操作的实质是除二，除三，除五。由此我们可以猜想在最优策略下，两块蛋糕最后的重量应该是[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]最大公约数和最小公倍数问题
很经典的问题了吧……然而现在才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 3713]Iloczyn
这题应该注意到，斐波纳契函数增长速度很快，[tex]10^9[/tex]以下的斐波纳契函数值很少，所以可以打表。这样，问题就迎刃而解了。
代码：
/**************************************************************
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]轻拍牛头
噫……筛法
然而……人傻自带大常数
代码：
