容斥原理专题(更新中……)

首先推荐一篇翻译过来的俄文论文
http://www.cnblogs.com/acSzz/archive/2012/11/18/2775923.html
uva10325
题意:整数区间[1,n],m个数a[1……m],且a[i]<=n,求区间[1,n]中不能被任意一个a[i]整除的数有多少
简单容斥

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef long long ll;
ll a[17];
ll ans;
ll n,m;
ll gcd(ll a,ll b)
{
	if(!b) return a;
	while(b)
	{
		ll t=a;
		a=b;
		b=t%b;
	
	}
	return a;
}
ll lcm(ll a,ll b)
{
	return a/gcd(a,b)*b;
}
void dfs(int flag,ll x,ll num)
{
	if(flag&1) ans+=n/num;
	else ans-=n/num;
	for(int i=x+1;i<=m;i++)
		dfs(flag+1,i,lcm(num,a[i]));
	return;
}
int main()
{
	int i;
	while(scanf("%lld %lld",&n,&m)!=EOF)
	{
		for(i=1;i<=m;i++)
			scanf("%lld",&a[i]);
		ans=0;
		for(i=1;i<=m;i++)
			dfs(1,i,a[i]);
		ans=n-ans;
		printf("%lld\n",ans);

	
	
	}

	return 0;
}

uva11806
题意:n*m的格子矩阵,要你涂色其中k个格子,使得第一行、最后一行、第一列、最后一列都至少有一格涂色(角上的格子代表着两行),问有多少种方案,结果mod 1000007
思路:思考它的逆问题,上述四行中至少一行没有被涂色的可能方案数。容斥解之。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
const int mod=1000007;
int c[510][510],a[5],b[5];
int ans,n,m,k;
void init()
{
    int i,j;
    memset(c,0,sizeof(c));
    for(i=0;i<=500;i++)
        c[i][0]=1;
    for(i=1;i<=500;i++)
        for(j=1;j<=i;j++)
        {
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
        }
    return;
}
void dfs(int flag,int x,int row,int col)
{
    if(flag&1)
        ans=(ans+c[row*col][k])%mod;
    else
        ans=(ans-c[row*col][k]+mod)%mod;
    for(int i=x+1;i<=4;i++)
      dfs(flag+1,i,row+a[i],col+b[i]);
    return;

}
int main()
{
    int i,t,cases=0;
    a[1]=-1,a[2]=0,a[3]=-1,a[4]=0;
    b[1]=0,b[2]=-1,b[3]=0,b[4]=-1;
    init();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d %d",&n,&m,&k);
        ans=0;
        for(i=1;i<=4;i++)
            dfs(1,i,n+a[i],m+b[i]);
        ans=(c[n*m][k]-ans+mod)%mod;
        printf("Case %d: %d\n",++cases,ans);
    }
    return 0;
}

TopCoder SRM 477
题意:n个数对应n个位置,其中k个确定的位置错排的方案有多少种
思路:思考反问题,设k个位置分别为pos[1],pos[2],……,pos[k].pos[i]不错排,其他k-1个位置错排的方案,pos[i]、pos[j]错排,其它k-2个位置不错排的方案,and so on……

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef long long ll;
const ll mod=1000000007;
ll n,k;
ll ans;
ll fact[1010];
ll mulmod(ll a,ll n,ll m)
{
    ll y=0;
    a%=m;
    while(n)
    {
        if(n&1) y+=a;
        if(y>=m) y-=m;
        n>>=1;
        a<<=1;
        if(a>=m) a-=m;
    }
    return y;
}
void dfs(int flag,int x,ll num)
{
    if(flag&1)
        ans=(ans+fact[n-num])%mod;
    else
        ans=(ans-fact[n-num]+mod)%mod;
    for(int i=x+1;i<=k;i++)
        dfs(flag+1,i,num+1);

}
int main()
{
    int i;
    fact[0]=1;
    for(i=1;i<=1000;i++)
    fact[i]=mulmod(fact[i-1],i,mod);
    while(scanf("%lld %lld",&n,&k)!=EOF)
    {
        ans=0;
        for(i=1;i<=k;i++)
            dfs(1,i,1);
        ans=(fact[n]-ans+mod)%mod;
        printf("%lld\n",ans);

    }
    return 0;
}

hdoj2204
一直用g++提交,一直wa,后来用c++,终于ac了。。
1.a^k<=n,那么显然对于<=a的数t,t^k<=n
2.若a^(k*t),则(a^k)^t.所以只要考虑指数为素数的情况即可。
3.a^3与t^7可能相同,所以要用容斥

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
typedef __int64 ll;
#define eps 1.0e-8
int a[5];
ll ans,n;
const int N=100;
int pr[N+10],p[N+10],lp;
void gp()
{
    for(int i=2;i<N;i++)
    {
        if(!pr[i])p[++lp]=pr[i]=i;
        for(int j=1;j<=lp && i*p[j]<N;j++)
        {
            pr[i*p[j]]=p[j];
            if(i%p[j]==0) break;
        }
    }
    return;
}
void dfs(int flag,int x,int num)
{
    int i;
    if(num>=60)
        return;
    ll tmp=(ll)pow((double)n+eps,1.0/num);

    if(flag&1)
        ans+=tmp;
    else
        ans-=tmp;
    for(i=x+1;i<=17;i++)
        dfs(flag+1,i,num*p[i]);
    return;
}
int main()
{
    int i;
    gp();
    while(scanf("%I64d",&n)!=EOF)
    {
        ans=0;
        for(i=1;i<=17;i++)
            dfs(1,i,p[i]);
        printf("%I64d\n",ans-1);
    }
    return 0;
}

zoj2836
简单那容斥,注意理解题意,any与every的区别。。

#include<stdio.h>
#include<stdlib.h>
typedef long long ll;
ll n,m,ans;
ll a[15];
ll gcd(ll a,ll b)
{
    if(a<b) a=a^b,b=a^b,a=a^b;
    if(!b) return a;
    while(b)
    {
        ll t=a;
        a=b;
        b=t%b;
    }
    return a;
}
ll lcm(ll a,ll b)
{
    return a/gcd(a,b)*b;
}
void dfs(ll flag,ll x,ll num)
{
    if(flag&1)
        ans+=m/num;
    else
        ans-=m/num;
    for(int i=x+1;i<=n;i++)
        dfs(flag+1,i,lcm(num,a[i]));
    return;
}
int main()
{
    int i,j;
    while(scanf("%lld %lld",&n,&m)!=EOF)
    {
        ans=0;
        for(i=1;i<=n;i++)
            scanf("%lld",&a[i]);
        for(i=1;i<=n;i++)
            dfs(1,i,a[i]);
        printf("%lld\n",ans);

    }
    return 0;
}

zoj3233
题意:分别给你n个正整数a[i],m个正整数b[i],数据范围[1,32767],同时给你两个整数low,up,数据范围[1,10^18],问你[low,up]区间内有多少个数满足:至少能被一个a[i]整除且至少能被一个b[i]不整除。
哈哈,这题独立想出来了特别高兴,应为感觉这题不是直接赤裸裸的容斥,而是要变化下。
思路:
1.[low,up]区间满足的数的个数=[1,up]区间满足的数的个数-[1,low-1]区间满足的数的个数。
2.能被a整除,且能被b整除,等价于能被lcm(a,b)整除
3.至少能被一个a[i]整除且至少能被一个b[i]不整除,转化一下:至少能被一个a[i]整除且不是能被所有b[i]整除。为了是思维清晰,符号化一下:
x:至少能被一个a[i]整除.
y:能被所有b[i]整除
原命题转化为:x && (非y)
发现还是不能直接用容斥,继续转化,最关键的转化:x && (非y)=x-(x && y)
也就是说:(a[1]表示能被a[1]整除的个数)
(能被所有b[i]整除,等价于能被lcm(b[1],b[2],b[3],……,b[m])整除(设为lcm))
(a[1] || a[2] || …… || a[n])-(a[1] || a[2] || …… || a[n]) && lcm就是答案
很显然,减号的前面部分是可以直接用容斥的,后面部分却带了一个 && lcm,肿么办呢?
其实这里考察的就是布尔代数的知识啦。
(a[1] || a[2] || …… || a[n]) && lcm=(a[1] && lcm) || (a[2] && lcm) || …… || (a[n] && lcm)
化成这样就可以使用容斥啦。
最后,分别对[1,up],[1,low-1]求解出满足的个数再相减就可以了。
本题这样就解决了吗?思路上这样确实对了,但是还有一个要注意的地方,这个地方往往被忽略(弱菜表示因为这个提交错了20次。。).
本题的a[i],b[i]是10^4级别,且b序列可能达到500个,这样最坏情况下,这些数的lcm是会llu溢出的,溢出说明区间中没有数能被这个数整除,因为这个数太大了。所以直接返回或continue即可。(可以lcm()函数里判断是否溢出,溢出返回0,这样在dfs等地方就很好判断是否溢出了,当然,也可以在溢出时,让lcm()返回一个>10^18的数,试了一下时间从690 ms升到1190 ms)
—————————————————我是分割线君————————————————
好吧,看了下网上别人的代码,其实可以更严格地考虑当a/gcd>up/b就返回up+1,也就是说当lcm大于up了,能被lcm整除的数一定为0了。

#include<stdio.h>
const unsigned long long inf=(1<<63)-1+(1<<63);
typedef unsigned long long ll;
int n,m;
ll a[20];
ll ans;
bool flag;
ll gcd(ll a,ll b)
{
    if(a<b) a=a^b,b=a^b,a=a^b;
    if(!b) return a;
    while(b)
    {
        ll t=a;
        a=b;
        b=t%b;
    }
    return a;
}
ll lcm(ll a,ll b)
{
    ll tmp=a/gcd(a,b);
    if(tmp>(inf/b))
        return 0;
    return tmp*b;
}
void dfs(ll flag,int x,ll num,ll b)
{
    if(num==0)
        return;
    if(flag&1)
        ans+=b/num;
    else
        ans-=b/num;
    for(int i=x+1;i<=n;i++)
    {
        if(a[i]==0)
            continue;
        dfs(flag+1,i,lcm(num,a[i]),b);
    }
    return;

}
ll solve(ll l,ll r)
{
    int i;
    ll result=0;
    ans=0;
    for(i=1;i<=n;i++)
        dfs(1,i,a[i],l);
    result+=ans;
    ans=0;
    for(i=1;i<=n;i++)
        dfs(1,i,a[i],r);
    result=ans-result;
    if(flag)
    {
        for(i=1;i<=n;i++)
        {
            a[i]=lcm(a[i],a[n+1]);
        }
        ans=0;
        for(i=1;i<=n;i++)
            dfs(1,i,a[i],l);
        result+=ans;
        ans=0;
        for(i=1;i<=n;i++)
            dfs(1,i,a[i],r);
        result-=ans;
    }
    return result;
}
int main()
{
    int i;
    ll l,r;
    scanf("%d %d %llu %llu",&n,&m,&l,&r);
    while(!(n==0 && m==0 && l==0 && r==0))
    {
        flag=1;
        for(i=1;i<=n;i++)
        {
            scanf("%llu",&a[i]);
        }
        a[n+1]=1;
        ll tmp;
        for(i=1;i<=m;i++)
        {
            scanf("%llu",&tmp);
            if(a[n+1]==0)
            {
                flag=0;
                continue;
            }
            a[n+1]=lcm(a[n+1],tmp);
        }
        ll result=solve(l-1,r);
        printf("%llu\n",result);
        scanf("%d %d %llu %llu",&n,&m,&l,&r);
    }
    return 0;
}

hdoj1796
简单容斥

#include<stdio.h>
typedef long long ll;
ll a[15];
ll n;
int m;
ll ans;
ll gcd(ll a,ll b)
{
    if(a>b) a=a^b,b=a^b,a=a^b;
    if(!b) return a;
    while(b)
    {
        ll t=a;
        a=b;
        b=t%b;
    }
    return a;
}
ll lcm(ll a,ll b)
{
    return a/gcd(a,b)*b;
}
void dfs(int flag,int x,ll num)
{
    if(flag&1)
        ans+=n/num;
    else
        ans-=n/num;
    for(int i=x+1;i<=m;i++)
    {
        if(a[i]==0)
            continue;
        dfs(flag+1,i,lcm(num,a[i]));
    }
    return;
}
int main()
{
    int i;
    while(scanf("%lld %d",&n,&m)!=EOF)
    {
        n--;
        ans=0;
        for(i=1;i<=m;i++)
        {
            scanf("%lld",&a[i]);
        }
        if(n==0)
        {
            printf("0\n");
            continue;
        }
        for(i=1;i<=m;i++)
        {
            if(a[i]==0)
                continue;
            dfs(1,i,a[i]);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

hdoj2841
开始把这题想的太简单了。
开始的错误思路,如图:

只考虑了和蓝色线共线的点,没考虑紫色线共线的点。
正确思路:可以发现,两个点与(0,0)在一条线上,那么a1/b1=a2/b2,也就是说加入两个点坐标(a,b),a与b不互质,则设a=a1*d,b=b1*d,那么a/b=a1/b1,也就是说(a,b)与(a1,b1)共线。那么本体就转化为找[1,n]、[1,m]有多少个互素对(交换位置算不同的互素对)

#include<stdio.h>
#include<string.h>
const int N=100000;
int pr[N+10],p[N];
int pi[N+5][30],ki[N+5][30];//这里数组大小开成log2(N)左右即可
int cnt,lp;
int ans;
int n,m;
void gp()
{
	for(int i=2;i<=N;i++)
	{
		if(!pr[i])
			p[++lp]=pr[i]=i;
		for(int j=1;j<=lp && i*p[j]<=N;j++)
		{
			pr[i*p[j]]=p[j];
			if(i%p[j]==0)break;
		}
	}
	return;
}
void fenjie(int n,int* pi,int* ki)
{
	cnt=0;
	memset(ki,0,sizeof(ki));
    while(n!=1)
	{
        int t=pr[n];
        pi[++cnt]=t;
        ki[cnt]=0;
        while(n%t==0)
        {
            n/=t;
            ki[cnt]++;
        }
    }
    pi[0]=cnt;
    return;
}
void dfs(int flag,int x,int num,int d)
{
    if(flag&1)
        ans+=m/num;
    else
        ans-=m/num;
    for(int i=x+1;i<=pi[d][0];i++)
        dfs(flag+1,i,num*pi[d][i],d);
    return;
}
int rongchi(int n)
{
    ans=0;
    for(int i=1;i<=pi[n][0];i++)
        dfs(1,i,pi[n][i],n);
    ans=m-ans;
    return ans;
}
__int64 solve()
{
    int i;
    __int64 result=0;
    for(i=1;i<=n;i++)
    {
        result+=(__int64)rongchi(i);
    }

    return result;
}
int main()
{
    int i;
    int t;
    gp();
    for(i=2;i<=N;i++)
        fenjie(i,pi[i],ki[i]);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&n,&m);
        if(n==1 || m==1)
        {
            int ans=(n==1?m:n);
            printf("%d\n",ans);
            continue;
        }
        __int64 result=solve();
        printf("%I64d\n",result);






    }

    return 0;
}

ural1091
题意:在[1,s]取k个不同的数,要求,这k个数有>1的公约数,给出k、s,求组数
思路:如果k个数含公因子p[i]、p[j],那么这些组肯定会重复计算。
ans=∑c(s/p[i],k)-∑c(s/(p[i]*p[j]),k)+……(p[i]是素数)

#include<stdio.h>
typedef long long ll;
int p[16]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
int s,k;
ll  ans;
int cc[45][45];
int c(int n,int m)
{
    if(m>n)
        return 0;
    return cc[n][m];
}
void dfs(int flag,int x,int num)
{
    if(num>s)
        return;
    if(flag&1)
        ans+=(ll)c(s/num,k);
    else
        ans-=(ll)c(s/num,k);
    for(int i=x+1;i<=15;i++)
        dfs(flag+1,i,num*p[i]);
    return;
}
int main()
{
    int i,j;
    for(i=0;i<=40;i++)
        cc[i][0]=1;
    for(i=1;i<=40;i++)
        for(j=1;j<=i;j++)
            cc[i][j]=cc[i-1][j-1]+cc[i-1][j];

    while(scanf("%d %d",&k,&s)!=EOF)
    {
        ans=0;
        for(i=1;i<=15;i++)
            dfs(1,i,p[i]);
        if(ans<10000)
            printf("%lld\n",ans);
        else
            printf("10000\n");

    }
    return 0;
}

URAL 1114
题意:a个相同的红球和b个相同的篮球放入n个不同的盒子,每个盒子可以为空,球可以不放。问有几种放球方案。
思路:
1.对于没放的球,可以抽象出一个盒子,这个盒子用于放没放的球,这样就解决了球可以不放的问题。
2.对于球的颜色,可以分别计算放红球的方法数,放篮球的方法数,乘法原理即可,可以这样做的原因在于:对于不同的红球方法,必有至少一个盒子里面的红球数不同,而对于每种红球方法,加上不同的篮球放法必然形成不同的放法。这样就解决了颜色问题
3.最后就是插板法计算每种球的方法了:c(n+a,n)、c(n+b,n)。最后答案两者相乘
4.注意要用高精度。。(尼玛,这次这个大数模板没出错,看来刚才wa的几题不是大数部分出错。。)

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXN 9999
#define MAXSIZE 1000
#define DLEN 4
using namespace std;
class BigNum;
istream& operator>>(istream&,  BigNum&);
ostream& operator<<(ostream&,  BigNum&);
class BigNum
{
public:
	int a[MAXSIZE];
	int len;
public:
	BigNum(){len = 1;memset(a,0,sizeof(a));}
	BigNum(const int);
	BigNum(const char*);
	BigNum(const BigNum &);
	BigNum &operator=(const BigNum &);
	friend istream& operator>>(istream&,  BigNum&);
	friend ostream& operator<<(ostream&,  BigNum&);
	BigNum operator+(const BigNum &) const;
	BigNum operator-(const BigNum &) const;
	BigNum operator*(const BigNum &) const;
	BigNum operator/(const int  &) const;
	BigNum operator^(const int  &) const;
	int    operator%(const int  &) const;
	bool   operator>(const BigNum & T)const;
	bool   operator==(const BigNum & T)const;
	bool   operator==(const int & t)const;
	bool   operator>(const int & t)const;
};
istream& operator>>(istream & in,  BigNum & b)
{
	char ch[MAXSIZE*4];
	int i = -1;
	in>>ch;
	int l=strlen(ch);
	int count=0,sum=0;
	for(i=l-1;i>=0;)
	{
		sum = 0;
		int t=1;
		for(int j=0;j<4&&i>=0;j++,i--,t*=10)
		{
			sum+=(ch[i]-'0')*t;
		}
		b.a[count]=sum;
		count++;
	}
	b.len =count++;
	return in;

}
ostream& operator<<(ostream& out,  BigNum& b)
{
	int i;
	cout << b.a[b.len - 1];
	for(i = b.len - 2 ; i >= 0 ; i--)
	{
		cout.width(DLEN);
		cout.fill('0');
		cout << b.a[i];
	}
	return out;
}
BigNum::BigNum(const int b)
{
	int c,d = b;
	len = 0;
	memset(a,0,sizeof(a));
	while(d > MAXN)
	{
		c = d - (d / (MAXN + 1)) * (MAXN + 1);
		d = d / (MAXN + 1);  a[len++] = c;
	}
	a[len++] = d;
}
BigNum::BigNum(const char*s)
{
	int t,k,index,l;
	memset(a,0,sizeof(a));
	l=strlen(s);
	len=l/DLEN;
	if(l%DLEN)len++;
	index=0;
	for(int i=l-1;i>=0;i-=DLEN)
	{
		t=0;k=i-DLEN+1;
		if(k<0)k=0;
		for(int j=k;j<=i;j++)
			t=t*10+s[j]-'0';
		a[index++]=t;
	}
}
BigNum::BigNum(const BigNum & T) : len(T.len)
{
	int i;
	memset(a,0,sizeof(a));
	for(i = 0 ; i < len ; i++)  a[i] = T.a[i];
}
BigNum & BigNum::operator=(const BigNum & n)
{
	len = n.len;
	memset(a,0,sizeof(a));
	for(int i = 0 ; i < len ; i++)
		a[i] = n.a[i];
	return *this;
}
BigNum BigNum::operator+(const BigNum & T) const
{
	BigNum t(*this);
	int i,big;
	big = T.len > len ? T.len : len;
	for(i = 0 ; i < big ; i++)
	{
		t.a[i] +=T.a[i];
		if(t.a[i] > MAXN)
		{
			t.a[i + 1]++;
			t.a[i] -=MAXN+1;
		}
	}
	if(t.a[big] != 0) t.len = big + 1;
	else t.len = big;
	return t;
}
BigNum BigNum::operator-(const BigNum & T) const
{
	int i,j,big;
	bool flag;
	BigNum t1,t2;
	if(*this>T)
	{
		t1=*this;
		t2=T;
		flag=0;
	}
	else
	{
		t1=T;
		t2=*this;
		flag=1;
	}
	big=t1.len;
	for(i = 0 ; i < big ; i++)
	{
		if(t1.a[i] < t2.a[i])
		{
			j = i + 1;
			while(t1.a[j] == 0) j++;
			t1.a[j--]--;
			while(j > i) t1.a[j--] += MAXN;
			t1.a[i] += MAXN + 1 - t2.a[i];
		}
		else t1.a[i] -= t2.a[i];
	}
	t1.len = big;
	while(t1.a[len - 1] == 0 && t1.len > 1)
	{
		t1.len--;
		big--;
	}
	if(flag)t1.a[big-1]=0-t1.a[big-1];
	return t1;
}
BigNum BigNum::operator*(const BigNum & T) const
{
	BigNum ret;
	int i,j,up;
	int temp,temp1;
	for(i = 0 ; i < len ; i++)
	{
		up = 0;
		for(j = 0 ; j < T.len ; j++)
		{
			temp = a[i] * T.a[j] + ret.a[i + j] + up;
			if(temp > MAXN)
			{
				temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);
				up = temp / (MAXN + 1);
				ret.a[i + j] = temp1;
			}
			else
			{
				up = 0;
				ret.a[i + j] = temp;
			}
		}
		if(up != 0)
			ret.a[i + j] = up;
	}
	ret.len = i + j;
	while(ret.a[ret.len - 1] == 0 && ret.len > 1) ret.len--;
	return ret;
}
BigNum BigNum::operator/(const int & b) const
{
	BigNum ret;
	int i,down = 0;
	for(i = len - 1 ; i >= 0 ; i--)
	{
		ret.a[i] = (a[i] + down * (MAXN + 1)) / b;
		down = a[i] + down * (MAXN + 1) - ret.a[i] * b;
	}
	ret.len = len;
	while(ret.a[ret.len - 1] == 0 && ret.len > 1) ret.len--;
	return ret;
}
int BigNum::operator %(const int & b) const
{
	int i,d=0;
	for (i = len-1; i>=0; i--)
	{
		d = ((d * (MAXN+1))% b + a[i])% b;
	}
	return d;
}
BigNum BigNum::operator^(const int & n) const
{
	BigNum t,ret(1);
	int i;
	if(n<0)exit(-1);
	if(n==0)return 1;
	if(n==1)return *this;
	int m=n;
	while(m>1)
	{
		t=*this;
		for( i=1;i<<1<=m;i<<=1){
			t=t*t;
		}
		m-=i;
		ret=ret*t;
		if(m==1)ret=ret*(*this);
	}
	return ret;
}
bool BigNum::operator>(const BigNum & T) const
{
	int ln;
	if(len > T.len) return true;
	else if(len == T.len)
	{
		ln = len - 1;
		while(a[ln] == T.a[ln] && ln >= 0) ln--;
		if(ln >= 0 && a[ln] > T.a[ln]) return true;
		else return false;
	}
	else return false;
}
bool BigNum::operator==(const BigNum & T) const
{
	int ln;
	if(len != T.len) return false;
	else
	{
		ln = len - 1;
		while(a[ln] == T.a[ln] && ln-- );
		if(ln < 0) return true;
		else return false;
	}
}
bool BigNum::operator >(const int & t) const
{
	BigNum b(t);
	return *this>b;
}
bool BigNum::operator==(const int & t) const
{
	BigNum b(t);
	return *this==b;
}
typedef BigNum ll;
ll cc[45][45];
ll c(int n,int m)
{
    if(m>n)
        return 0;
    return cc[n][m];
}
int main()
{
    int i,j;
    for(i=0;i<=40;i++)
        cc[i][0]=1;
    for(i=1;i<=40;i++)
        for(j=1;j<=i;j++)
            cc[i][j]=cc[i-1][j-1]+cc[i-1][j];
    int n,a,b;
    while(scanf("%d%d%d",&n,&a,&b)!=EOF)
    {
        ll ans=c(n+a,n)*c(n+b,n);
        cout<<ans<<endl;
    }
    return 0;
}

poj1091
关键是要知道最大公约数相关定理,本博客中已转载

#include<stdio.h>
typedef long long ll;
ll n,m;
const ll N=1000000;
ll pr[N+10],p[(N+10)/10],lp;
void gp()
{
	for(ll i=2;i<=N;i++)
	{
		if(!pr[i]) p[++lp]=pr[i]=i;
		for(ll j=1;j<=lp && i*p[j]<=N;j++)
		{
			pr[i*p[j]]=p[j];
			if(i%p[j]==0) break;
		}
	}
	return;
}
ll cnt;//b数组用来存放n分解后的素因子
ll b[50];
void gn(ll n)
{
	ll i,t;
	cnt=0;
	while(n>1)
	{
		if(n<=N) //判断n是否小于等于10^6,当大于10^6时,它肯定含有p[1—lp]范围内的素数(如果不含,那么必然是素数,否则它含有大于10^6的素数,则它>10^12)
			t=pr[n];//小于的时候直接log级别分解
		else
		{
			t=n;
			for(i=1;i<=lp && p[i]<=n/p[i];i++)
				if(n%p[i]==0)
				{
					t=p[i];
					break;
				}
		}
		while(n%t==0) n/=t;
			b[++cnt]=t;
	}
	return;
}
ll ans;
ll cal(ll x)
{
    ll result=1;
    for(ll i=1;i<=n;i++)
    {
        result*=x;
    }
    return result;

}
void dfs(int flag,ll x,ll num)
{
    ll tmp=cal(m/num);
    if(flag&1)
        ans+=tmp;
    else
        ans-=tmp;
    for(ll i=x+1;i<=cnt;i++)
    {
        dfs(flag+1,i,num*b[i]);
    }
    return;
}
int main()
{
    ll i;
    gp();
    while(scanf("%lld %lld",&n,&m)!=EOF)
    {
        ans=0;
        gn(m);
        for(i=1;i<=cnt;i++)
            dfs(1,i,b[i]);
        ans=cal(m)-ans;
        printf("%lld\n",ans);
    }
    return 0;
}

hdoj4135
简单容斥

#include<stdio.h>
typedef __int64 ll;
ll n,a,b;
const int N=1000000;
ll pr[N+10],p[(N+10)/10],lp;
void gp()
{
	for(int i=2;i<=N;i++)
	{
		if(!pr[i]) p[++lp]=pr[i]=i;
		for(int j=1;j<=lp && i*p[j]<=N;j++)
		{
			pr[i*p[j]]=p[j];
			if(i%p[j]==0) break;
		}
	}
	return;
}
int cnt;
ll pp[30];//b数组用来存放n分解后的素因子
void gn(ll n)
{
	int i,t;
	cnt=0;
	while(n>1)
	{
		if(n<=N) //判断n是否小于等于10^6,当大于10^6时,它肯定含有p[1—lp]范围内的素数(如果不含,那么必然是素数,否则它含有大于10^6的素数,则它>10^12)
			t=pr[n];//小于的时候直接log级别分解
		else
		{
			t=n;
			for(i=1;i<=lp && p[i]<=n/p[i];i++)
				if(n%p[i]==0)
				{
					t=p[i];
					break;
				}
		}
		while(n%t==0) n/=t;
			pp[++cnt]=t;
	}
	return;
}
ll ans;
void dfs(int flag,int x,ll num,ll n)
{
    if(num>n)
        return;
    if(flag&1)
        ans+=n/num;
    else
        ans-=n/num;
    for(int i=x+1;i<=cnt;i++)
    {
        if(num*pp[i]<=n)
            dfs(flag+1,i,num*pp[i],n);
    }
    return;
}
int main()
{
    int t,i,cases=0;
    gp();
    scanf("%d",&t);
    while(t--)
    {
        ans=0;
        scanf("%lld %lld %lld",&a,&b,&n);
        gn(n);
        for(i=1;i<=cnt;i++)
            dfs(1,i,pp[i],a-1);
        ll tmp=ans;
        ans=0;
        for(i=1;i<=cnt;i++)
            dfs(1,i,pp[i],b);
        ans=ans-tmp;
        ans=b-a+1-ans;
        printf("Case #%d: %lld\n",++cases,ans);
     }
    return 0;
}

poj2773
二分+容斥
一开始以为二分完就可以了,其实还要判断当前答案是否与m互质,如果不互质,还要继续减下去。

#include<stdio.h>
#include<string.h>
typedef long long ll;
const ll inf=100000000000000000;
const int N=1000000;
ll pr[N+10],p[N];
ll pi[N],ki[N];//这里数组大小开成log2(N)左右即可
int cnt,lp;
ll m,k;
ll gcd(ll a,ll b)
{
    if(a<b) a=a^b,b=a^b,a=a^b;
    if(!b) return a;
    while(b)
    {
        ll t=a;
        a=b;
        b=t%b;
    }
    return a;
}
void gp()
{
	for(int i=2;i<=N;i++)
	{
		if(!pr[i])
			p[++lp]=pr[i]=i;
		for(int j=1;j<=lp && i*p[j]<=N;j++)
		{
			pr[i*p[j]]=p[j];
			if(i%p[j]==0)break;
		}
	}
	return;
}
void fenjie(ll n)
{
	cnt=0;
	memset(ki,0,sizeof(ki));
	while(n!=1)
	{
		ll t=pr[n];
        pi[++cnt]=t;ki[cnt]=0;
        while(n%t==0)
        {
            n/=t;ki[cnt]++;
        }
    }
    return;
}
ll ans;
void dfs(int flag,int x,ll num,ll n)
{
    if(flag&1)
        ans+=n/num;
    else
        ans-=n/num;
    for(int i=x+1;i<=cnt;i++)
    {
        if(num*pi[i]<=n)
            dfs(flag+1,i,num*pi[i],n);
    }
    return;
}
int main()
{
    int i,j;
    gp();
    while(scanf("%lld %lld",&m,&k)!=EOF)
    {
        ans=0;
        ll result=0;
        fenjie(m);
        ll l=1,r=inf,mid;
        while(l<=r)
        {
            ans=0;
            mid=l+(r-l)/2;
            for(i=1;i<=cnt;i++)
                dfs(1,i,pi[i],mid);
            ans=mid-ans;
            if(ans==k)
            {
                result=mid;
                break;
            }
            else if(ans>k)
                r=mid-1;
            else
                l=mid+1;
        }
        result=mid;

        while(gcd(result,m)!=1)
        {
            result--;
        }

        printf("%lld\n",result);




    }

    return 0;
}

zoj3687
终于ac了,纠结了好一阵子,居然是变量名错了。
关键点:冲突的条件不可能同时成立,所以要判断这种情况。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define mod 55566677
using namespace std;
bool day[55],cha[55];
bool hash[55][55];
typedef long long ll;
typedef struct node{
    int d,c;
}node;
node a[30];
ll fact[55];
int n,m;
ll ans;
void dfs(int flag,int x,int num)
{
    day[a[x].d]=1;cha[a[x].c]=1;
    if(flag&1)
    {
        ans=((ans-fact[n-num])%mod+mod)%mod;
    }
    else
    {
        ans=(ans+fact[n-num])%mod;
    }
    for(int i=x+1;i<=m;i++)
    {
        if((day[a[i].d]==1) || (cha[a[i].c]==1)) continue;
        dfs(flag+1,i,num+1);
        day[a[i].d]=0;cha[a[i].c]=0;
    }
    return;
}
int main()
{
    int i;
    fact[0]=1;fact[1]=1;
    for(i=2;i<=50;i++)
        fact[i]=fact[i-1]*(ll)i%mod;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(day,0,sizeof(day));
        memset(cha,0,sizeof(cha));
        memset(hash,0,sizeof(hash));
        int cnt=0;
        for(i=1;i<=m;i++)
        {
            int d,c;
            scanf("%d%d",&d,&c);
            if(hash[d]1) continue;
            a[++cnt].d=d;a[cnt].c=c;
            hash[d]1=1;
        }
        m=cnt;
        ans=fact[n];
        for(i=1;i<=m;i++)
        {
            dfs(1,i,1);
            day[a[i].d]=0;cha[a[i].c]=0;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

hdoj1025

LIS+单调队列优化

#include<stdio.h>
#include<algorithm>
#define N 100000+10
#define inf 1000000000
using namespace std;
typedef struct Node{
	int p,r;
}Node;
Node node[N];
int b[N];
bool cmp(Node a,Node b)
{
	return a.p<b.p;
}
int main()
{
	int i,j;
	int n,cases=0;
	while(scanf("%d",&n)!=EOF)
	{
		for(i=1;i<=n;i++)
		{
			int p,r;
			scanf("%d %d",&p,&r);
			node[i].p=p;
			node[i].r=r;
			b[i]=inf;
		}
		sort(node+1,node+1+n,cmp);
		for(i=1;i<=n;i++)
		{
			int* index=lower_bound(b+1,b+1+n,node[i].r);
			b[index-b]=node[i].r;
		}
		for(i=n;i>=1;i--)
			if(b[i]!=inf)
				break;
		printf("Case %d:\nMy king, at most %d %s can be built.\n\n",++cases,i,i==1?"road":"roads");

	
	}

	//system("pause");
	return 0;
}

数论专题

基础应用:
hdoj3501

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define ll __int64
#define mod 1000000007
ll phi(int n)
{
    int m = floor(sqrt(n+0.5));
    ll ans = n;
    for(int i = 2; i <= m; i++)
		if(n%i == 0)
		{
			ans = ans / i * (i-1);
			while(n%i == 0)
			{
				n /= i;
			}
		}
    if(n > 1)
		ans = ans / n *(n-1);
    return ans;
}
ll mulmod(ll a,ll n,ll m){
    ll y=0;
    a%=m;
    while(n){ 
        if(n&1) y+=a;
        if(y>=m) y-=m;
        n>>=1;
        a<<=1;
        if(a>=m) a-=m;
    }
    return y;
}

int main()
{
	int n,i;
	scanf("%d",&n);
	while(n!=0)
	{
		ll tmp=n-1-phi(n);
		if(tmp&1)
			n/=2;
		else
			tmp/=2;
		ll	ans=mulmod(tmp,(ll)n,(ll)mod);
		printf("%I64d\n",ans);
		
		

		scanf("%d",&n);
	}
	system("pause");
	return 0;
}

hdoj1215

#include<stdio.h>
#include<string.h>
#define N 500000
int sum[N+10];
void yueshu()
{
	int i,j;
	for(i=1;i<=N/2;i++)
	{
		for(j=2*i;j<=N;j+=i)
		{
			if(j>N) break;
			sum[j]+=i;
		}
	}
	return;

}
int main()
{
	int t;
	memset(sum,0,sizeof(sum));
	yueshu();
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		printf("%d\n",sum[n]);
		
	
	
	
	}
	return 0;
}

hdoj2136
用普通的筛选法筛出素数,然后记录每个素数在素数表里的位置,pr[]数组记录的是每个数的最大素因子
注意:这里的筛选素数不能写成

for(i=2;i*i<=N;i++)
{	
    if(!pr[i])
    {
	p[++lp]=i;
	pos[i]=lp;
	for(j=i*i;j<=N;j+=i)
	pr[j]=i;
    }
}

这样会出错,对于sqrt(N)的素数没有用来更新它的倍数,这样它的倍数的pr[]也没有更新,另外若i是素数,也没更新pr[i]

#include<stdio.h>
const int N=1000000;
int pr[N+10],p[N/10+10],lp;
int pos[N+10];
void gp(){
	int i,j;
    for(i=2;i<=N;i++)
	{	
		if(!pr[i])
		{
			p[++lp]=i;
			pos[i]=lp;
			for(j=i;j<=N;j+=i)
				pr[j]=i;
		}
    }
	return;
}
int main()
{
	int i,j;
	int n;
	gp();
	while(scanf("%d",&n)!=EOF)
	{
		if(n==1)
		{
			printf("0\n");
			continue;
		}
		
		printf("%d\n",pos[pr[n]]);
	
	
	}
	return 0;

}

poj2689
筛两次,注意细节

#include<stdio.h>
#include<string.h>
bool p[50010];
bool pr[1000000+10];
int prime[1000000+10];
void gp()
{
	int i,j;
	p[1]=0;
	memset(p,1,sizeof(p));
	for(i=2;i*i<=50000;i++)
	{
		if(p[i])
		{
			for(j=i*i;j<=50000;j+=i)
			{
				p[j]=0;
			}
		}
	}
	return;
}
void gp2(__int64 l,__int64 r)
{
	__int64 i,j;
	memset(pr,1,sizeof(pr));
	if(l==1)
		pr[1]=0;
	for(i=2;i*i<=r;i++)
	{
		if(i*i>r)
			break;
		if(p[i])
		{
			j=i*i;
			if(j<l)
			{
				j=(l/i)*i;
				if(j<l)
					j+=i;
			}
			for(;j<=r;j+=i)
			{
				if(j>r) break;
				pr[j-l+1]=0;
			}
		}
	}
	return;
}
int main()
{
	__int64 i;
	__int64 l,r;
	gp();
	while(scanf("%I64d %I64d",&l,&r)!=EOF)
	{
		gp2(l,r);
		int cnt=0;
		for(i=l;i<=r;i++)
		{
			if(pr[i-l+1])
				prime[++cnt]=i;
		}
		if(cnt<=1)
		{
			printf("There are no adjacent primes.\n");
			continue;
		}
		int min=1000000+10,max=-1,minx,miny,maxx,maxy;
		for(i=1;i<=cnt-1;i++)
		{
			if(prime[i+1]-prime[i]<min)
			{
				min=prime[i+1]-prime[i];
				minx=prime[i];
				miny=prime[i+1];
			
			}
			if(prime[i+1]-prime[i]>max)
			{
				max=prime[i+1]-prime[i];
				maxx=prime[i];
				maxy=prime[i+1];
			}
		
		}
		printf("%d,%d are closest, %d,%d are most distant.\n",minx,miny,maxx,maxy);
	
	}


	return 0;
}

hdoj4474
这题思路很巧妙,如果枚举n的倍数显然超时,而且这个答案可能非常大,无法用long long存储。
正确方法是用可用的数字bfs,如果当前状态下除以n的余数前面状态得到过,那么这个就不用进队了,因为显然由前面的那个状态进行搜索更优,这样队列中最多10000左右的元素,状态间要记录前驱。开始没有记录前驱,而是直接每个状态都开个字符串,最后MLE。。
然后又是被一个小错误弄的RE好多次。。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxn 10010
char use[11];
typedef struct node{
	char num;
	short mod;
	short pre;
}node;
bool has[maxn];
short n,m;
char cnt;
char ans[maxn];
node q[maxn];
short anscnt;
bool bfs()
{
	short i,j;
	memset(has,0,sizeof(has));
	int iq=0;
	node sr;
	for(i=1;i<=cnt;i++)
	{

		if(use[i]==0)
			continue;
		sr.mod=use[i]%n;
		if(has[sr.mod]==1) continue;
		has[sr.mod]=1;
		sr.pre=-1;
		sr.num=use[i];
		if(sr.mod==0)
		{
			ans[++anscnt]=use[i];
			return 1;
		}
		q[iq++]=sr;
	}
	for(i=0;i<=iq-1;i++)
	{
		int mod=q[i].mod;
		for(j=1;j<=cnt;j++)
		{
			int yushu=((mod*(10%n))%n+use[j]%n)%n;
			if(has[yushu]) continue;
			has[yushu]=1;
			node tmp;
			tmp.mod=yushu;
			tmp.pre=i;
			tmp.num=use[j];
			if(tmp.mod==0)
			{
				ans[++anscnt]=tmp.num;
				int cur=tmp.pre;
					while(cur!=-1)
					{
						ans[++anscnt]=q[cur].num;
						cur=q[cur].pre;
					}
				return 1;
			
			}
			q[iq++]=tmp;

		}
	}
	return 0;
}
int main()
{
	short i,j;
	int cases=0;
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		if(m==10)
		{
			for(i=1;i<=m;i++)
			{
				char tmp;
				scanf("%d",&tmp);
			}
			printf("Case %d: ",++cases);
			printf("-1\n");

			continue;
		}
		bool digit[12];
		anscnt=0;
		memset(digit,1,sizeof(digit));
		for(i=1;i<=m;i++)
		{
			int tmp;
			scanf("%d",&tmp);
			digit[tmp]=0;
		}
		cnt=0;
		for(i=0;i<=9;i++)
		{
			if(digit[i]==1)
				use[++cnt]=i;
		}
		bool flag=bfs();
		printf("Case %d: ",++cases);
		if(flag)
		{
			for(int tt=anscnt;tt>=1;tt--)
				printf("%d",ans[tt]);
			printf("\n");
		}
		else
			printf("-1\n");


	
	
	}
	return 0;
}

poj1845
对a进行分解质因数,但是由于是a^b,所以a^b的质因子指数非常大,所以构造矩阵快速计算pi^1+pi^2+……+pi^ki %mod
矩阵为:
pi pi
0 1
开始的思路是O(n)时间预处理出2——50000000每个数的最小质因数,然后常数时间对a分解质因数,结果无情的MLE了。。
改成sqrt(n)时间分解质因数就能AC了

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
const int maxn=3100000;
const int mod=9901;
int cnt;
__int64 p[maxn],k[maxn];
void fenjie(int n)
{
	cnt=0;
	for(int i=2;i*i<=n;i++)
	{
		if(n%i == 0)
		{
			p[++cnt]=i;
			k[cnt]=0;
			while(n%i==0)
			{
				n/=i;
				k[cnt]++;
			}
		}
	}
	if(n > 1)
	{
		p[++cnt]=n;
		k[cnt]=1;
	}
	return;
}
typedef struct Mat{
	__int64 m[3][3];
}Mat;
Mat per;
Mat multi(Mat a,Mat b)
{
	int i,j,k;
	Mat ans;
	for(i=1;i<=2;i++)
		for(j=1;j<=2;j++)
		{
			__int64 tmp=0;
			for(k=1;k<=2;k++)
				tmp=(tmp+a.m[i][k]*b.m[k][j])%mod;
			ans.m[i][j]=tmp;	
		}
	return ans;

}
Mat pow(Mat a,__int64 k)
{
	Mat ans=per,p=a;
	while(k)
	{
		if(k&1)
		{
			k--;
			ans=multi(ans,p);
		}
		else
		{
			k/=2;
			p=multi(p,p);
		}
	}
	return ans;
}
int main()
{
	int i,j;
	int a,b;
	Mat aa;
	for(i=1;i<=2;i++)
		for(j=1;j<=2;j++)
			per.m[i][j]=(i==j);
	while(scanf("%d %d",&a,&b)!=EOF)
	{
		fenjie(a);
		__int64 ans=1;
		for(i=1;i<=cnt;i++)
		{
			k[i]*=b;
			aa.m[1][1]=p[i];aa.m[1][2]=p[i];aa.m[2][1]=0;aa.m[2][2]=1;
			Mat tmp=pow(aa,k[i]);
			__int64 tt=(tmp.m[1][2]+1)%mod;
			ans=(ans*tt)%mod;
		}
		printf("%I64d\n",ans);
	
	
	
	
	
	}

	return 0;
}

poj1061
在zxs大神的帮助下终于ac了,orz一下^_^
wa的关键点在于自己对求方程通解的原理原来并不理解深刻,只是生搬硬套,导致错误。理解很重要啊
设d=gcd(a,b)
ax+by=d的初解是(x,y),那么ax0-by0=0加到该方程上一定还是成立的(因为加了0嘛。。)得到:
a(x+x0)+b(y-y0)=d。ax0=by0,可见a是ax0的约数,b是ax0的约数,所以ax0=by0一定是a和b的公倍数,那么要不漏掉任何解的话ax0自然要取最小,即ax0=by0=lcm(a,b)(设为lcm).如此可见,通解为(x+k*(lcm/a),y-k*(lcm/b))
再来考虑ax+by=c与ax+by=d的关系,显然在后面那个方程两边乘上c/d就得到了方程ax+by=c.所以得到ax+by=c的初解是(x*c/d,y*c/d)。那么它的通解呢。我们可以用分析ax+by=d的通解的方法来分析。
在ax+by=c基础上加上ax0-by0=0方程仍然成立。由于从ax+by=d到ax+by=c,系数a、b没有变,所以x0,y0也没变。这样,就得到ax+by=c的通解为(x*(c/d)+k*(lcm/a),y*(c/d)-k*(lcm/b))

#include<stdio.h>
#include<stdlib.h>
void exgcd(__int64 a,__int64 b,__int64 &d,__int64 &x,__int64 &y)
{
	if (!b) d=a,x=1,y=0;
	else
	{
		exgcd(b,a%b,d,y,x);
		y-=a/b*x;
	}
	return;
}
int main()
{
	__int64 x,y,m,n,L;
	while(scanf("%I64d %I64d %I64d %I64d %I64d",&x,&y,&m,&n,&L)!=EOF)
	{
		x=x%L;
		y=y%L;
		__int64 a=n-m;
		__int64 b=L;
		__int64 c=x-y;
		if(a==0)
		{
			printf("Impossible\n");
			continue;
		}
		if(c<0)
		{
			c=-c;
			a=-a;
		}
		__int64 xx,yy,d;
		if(a>0)
		{
			exgcd(a,b,d,xx,yy);
			if(c%d!=0)
			{
				printf("Impossible\n");
				continue;
			}
			xx*=c/d;
			xx=xx%(b/d);
			if(xx<0)
				xx=b/d+xx;
			printf("%I64d\n",xx);
		
		}
		else
		{
			a=-a;
			exgcd(a,b,d,xx,yy);
			if(c%d!=0)
			{
				printf("Impossible\n");
				continue;
			}
			xx*=c/d;
			xx=xx%(b/d);
			if(xx>0)
				xx-=b/d;
			
			printf("%I64d\n",-xx);				
		
		}
	}
	//system("pause");
	return 0;
}

hdoj2588
题意:给出n、m,求1<=x<=n,且gcd(x,n)>=m的这样的x有多少个
思路来自网上。。悲剧,想不到啊,以下是自己的一些总结
假设k是n的约数且k>=m,并设b与n/k互质,那么b和n/k都乘上k之后,得到n与bk,他们的最大公约数是k>=m。这里用到的关键一点就是:如果a与b互质,那么a*t与b*t的最大公约数是t。
那么只要找出所有phi(n/k)就可以了。(k是>=m的n的约数),答案就是所有phi(n/k)之和。
一个问题:设b1是与n/k1互质的数,b2是与n/k2互质的数,是否可能b1k1、b2k2相等?如果可能的话,就会造成重复计算
答:其实是不可能的。因为b1与n/k1互质,所以b1k1与最大公约数为k1,同理:b2k2与最大公约数为k2
证:假设b1k1=b2k2。
(1) 如果b1=b2,因为k1、k2是n的不同的约数,所以b1k1!=b2k2。
(2) 如果b1!=b2。
假设k1>k2,那么显然b2k2的最大真约数是k1,而k1又是n的约约数,可见b2k2与n的最大公约数是k1,这与b2k2与n的最大公约数是k2矛盾。
k1

#include<stdio.h>
__int64 phi(__int64 n)
{
	__int64 ans = n;
	for(__int64 i = 2; i*i<= n; i++)
		if(n%i == 0)
		{
			ans = ans / i * (i-1);
			while(n%i == 0)
			{
				n /= i;
			}
		}
	if(n > 1)
		ans = ans / n *(n-1);
	return ans;
}
int main()
{
	int t,i,j;
	__int64 n,m;
	scanf("%d",&t);
	while(t–)
	{
		scanf("%I64d %I64d",&n,&m);
		if(m==1)
		{
			printf("%I64d\n",n);
			continue;
		
		}
		__int64 result=0;
		for(i=1;i*i<=n;i++)
		{
			if(n%i!=0) continue;
			if(i<m)
			{
				if(n/i>=m)
					result+=phi(i);
			}
			else if(i>=m)
			{
				result+=phi(n/i);
				if(n/i>=m && i*i!=n)
					result+=phi(i);
			
			}
		}
		
			
		printf("%I64d\n",result);


	}
	return 0;
}

hdoj1788
解模线性方程组

#include<stdio.h>
typedef __int64 ll;
void exgcd(ll a,ll b,ll &d,ll &x,ll &y)
{
	if (!b) d=a,x=1,y=0;
	else
	{
		exgcd(b,a%b,d,y,x);y-=a/b*x;
	}
	return;
}
int main()
{
	int n,i,aa;
	while(scanf("%d %d",&n,&aa)!=EOF && !(n==0 && aa==0))
	{
		ll a1,r1,a2,r2;
		scanf("%I64d",&a1);
		r1=a1-aa;
		for(i=2;i<=n;i++)
		{
			scanf("%I64d",&a2);
			r2=a2-aa;
			ll a=a1,b=a2,c=r2-r1;
			ll d,x,y;
			exgcd(a,b,d,x,y);
			ll t=b/d;
			x=((x*c/d)%t+t)%t;
			r1=a1*x+r1;
			a1=a1/d*a2;
		}
		printf("%I64d\n",r1);
	}
	return 0;
}

hdoj1299
题意:对于1/x+1/y=1/n。(1<=x<=y,x、y为整数,n已知)。求满足方程的x、y有多少对。
尼玛。。。想不出来,看了别人思路。。罪过。。
思路:显然x>=n,y>=n。那么可以假设y=x+k。代入方程得到x=n+((n^2)/k)。那么显然必须(n^2)/k是整数。
则k必然是(n^2)的因子。解的个数其实就是k的个数。而且因为x<=y,所以k>=n,k的个数就是n^2的因子数,但是n^2可能达到2^18,很大。其实只要对n分解素因素即可,假设n分解后为n=p1^k1+p2^k2+……+pm^km.那么n的因子个数为(k1+1)(k2+1)……(km+1)。而n^2的因子个数很显然是(2*k1+1)(2*k2+1)……(2*km+1).那么满足k>=n的k的可能个数就是(ans+1)/2(为什么呢?因为因子是对称的嘛。。对于n^2来说,有一个小于n的因子k,必有一个大于n的因子(n^2)/k)

#include<stdio.h>
#include<string.h>
typedef __int64 ll;
const int N=1000000;
ll pr[N+10],p[(N+10)/10],lp;
void gp()
{
	for(ll i=2;i<=N;i++)
	{
		if(!pr[i]) p[++lp]=pr[i]=i;
		for(int j=1;j<=lp && i*p[j]<=N;j++)
		{
			pr[i*p[j]]=p[j];
			if(i%p[j]==0) break;
		}
	}
	return;
}
ll b[30],k[30];
int cnt;
void gn(ll n)
{
	int i;
	ll t;
	cnt=0;
	memset(k,0,sizeof(k));
	while(n>1)
	{
		if(n<=N)
		{
			t=pr[n];
		}
		else
		{
			t=n;
			for(i=1;i<=lp && p[i]<=n/p[i];i++)
				if(n%p[i]==0)
				{
					t=p[i];
					break;
				}
		}
		b[++cnt]=t;
		while(n%t==0)
		{
			n/=t;
			k[cnt]++;
		}
	}
	return;
}
int main()
{
	int t,cases=0;
	int i;
	gp();
	scanf("%d",&t);
	while(t--)
	{
		ll n;
		ll ans=1;
		scanf("%I64d",&n);
		gn(n);
		for(i=1;i<=cnt;i++)
			ans*=(2*k[i]+1);
		ans=(ans+1)/2;
		printf("Scenario #%d:\n%I64d\n\n",++cases,ans);
		
	}
	return 0;
}

hdoj1695
题意:给你两个区间[1,a],[1,b],问你两个区间各选一个整数x,y,gcd(x,y)=k的有多少对(无序对).
思路:gcd(x,y)=d,说明x/d、y/d互质。因为是无序的,所以先给定次序x<=y,问题转化为[1,a/d][1,b/d]两个区间各选x、y,满足x、y互质的对数有多少。设b=a/d,d=b/d,假设b是小区间,那么:
对于<=b的y,显然结果就是[1,b]每个数的欧拉函数值之和。
对于>b的y,要找到与y互质的且<=b的x有多少,这时欧拉函数失效了。可以用容斥求出[1,b]区间与y不互质的数有多少,然后b减去不互质的数的数量就是与y互质且<=b的x的数量。当然先要对y分解素因素。因为y<=10^5,所以可以预处理素数,log时间分解素因素。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef __int64 ll;
const int N=100000;
ll pr[N+10],p[N+10];
ll phi[N+10];
int cnt,lp;
void gp(){
	for(int i=2;i<=N;i++)
	{
		if(!pr[i]) p[++lp]=pr[i]=i;
		for(int j=1;j<=lp && i*p[j]<=N;j++)
		{
			pr[i*p[j]]=p[j];
			if(i%p[j]==0) break;
		}
	}
	return;
}
void oula()
{
	int i,j;
	for(i=1;i<=N;i++)
		phi[i]=i;
	for(i=1;i<=lp;i++)
	{
		for(j=p[i];j<=N;j+=p[i])
		{
			phi[j]=phi[j]/p[i]*(p[i]-1);
		}
	}
	return;
}
ll pi[30],ki[30];
void fenjie(int n)
{
	cnt=0;
	memset(ki,0,sizeof(ki));
	while(n!=1)
	{
		ll t=pr[n];
		pi[++cnt]=t;
		ki[cnt]=0;
		while(n%t==0)
		{
			n/=t;
			ki[cnt]++;
		}
	}
	return;
}
ll sum[N+10];
ll ans;
void dfs(int flag,int x,ll p,ll a)
{
	if(flag&1)
		ans+=a/p;
	else
		ans-=a/p;
	for(int i=x+1;i<=cnt;i++)
		dfs(flag+1,i,p*pi[i],a);
	return;
}
int main()
{
	int i,j;
	int t,cases=0;
	ll a,b,c,d,k;
	gp();
	oula();
	sum[1]=phi[1];
	for(i=2;i<=N;i++)
		sum[i]=sum[i-1]+phi[i];
	scanf("%d",&t);
	while(t--)
	{
		scanf("%I64d %I64d %I64d %I64d %I64d",&a,&b,&c,&d,&k);
		if(k==0 || (k>b && k>d))
		{
			printf("Case %d: 0\n",++cases);
			continue;
		}
		a=b/k;b=d/k;
		if(a>b){a=a^b;b=a^b;a=a^b;}
		if(a==b)
		{
			printf("Case %d: %I64d\n",++cases,sum[b]);
			continue;
		}
		ll result=sum[a];
		for(i=a+1;i<=b;i++)
		{
			fenjie(i);
			ans=0;
			for(j=1;j<=cnt;j++)
				dfs(1,j,pi[j],a);
			ans=a-ans;
			result+=ans;
		}
		printf("Case %d: %I64d\n",++cases,result);
	}
	return 0;
}

Codeforces 264B (Good Sequences)
题意:给你序列a1,a2,a3,……,an。n<=10^5,1<=ai<=10^5,严格升序给出。要你求出任意相邻数不互质的严格升序子序列最大长度。
O(n^2)的dp是很好想到的,方程:dp[i]=max{dp[j]|1<=j 需要换一种dp的形式。可以用dp[i]表示以序列中含素因子i的最后一个数结尾的子序列最大长度,显然:每次读入一个数,他都可以加在含它的素因子的数结尾的子序列后面,所以每次读入a[i]的时候,只需找出含它的素因子的数结尾的最长长度,并在这个长度上+1根新他的素因子即可

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef __int64 ll;
const int N=100000;
int pr[N+10],p[N+10];
int cnt,lp;
int max(int a,int b)
{
	return a>b?a:b;
}
void gp(){
	for(int i=2;i<=N;i++)
	{
		if(!pr[i]) p[++lp]=pr[i]=i;
		for(int j=1;j<=lp && i*p[j]<=N;j++)
		{
			pr[i*p[j]]=p[j];
			if(i%p[j]==0) break;
		}
	}
	return;
}
void fenjie(int n,int *pp)
{
	cnt=0;
	while(n!=1)
	{
		int t=pr[n];
		pp[++cnt]=t;
		while(n%t==0)
			n/=t;
	}
	pp[0]=cnt;
	return;
}
int a[N+10],dp[N+10];
int pp[N+10][30];
int main()
{
	int i,j;
	int n;
	gp();
	for(i=2;i<=N;i++)
		fenjie(i,pp[i]);
	pp[1][0]=0;
	while(scanf("%d",&n)!=EOF)
	{
		if(n==1)
		{
			scanf("%d",&a[1]);
			printf("1\n");
			continue;
		}
		memset(dp,0,sizeof(dp));
		for(i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			if(a[i]==1)
				continue;
			int tmp=-1;
			for(j=1;j<=pp[a[i]][0];j++)
			{
				tmp=max(tmp,dp[pp[a[i]][j]]);
			}
			for(j=1;j<=pp[a[i]][0];j++)
			{
				dp[pp[a[i]][j]]=tmp+1;
			}
		}
		int max=-1;
		for(i=2;i<=N;i++)
			if(dp[i]>max)
				max=dp[i];
		printf("%d\n",max);
	}


	return 0;
}

hdoj4483
好难,还没理清楚。。
先放上pick定理:pick定理:在一个平面直角坐标系内,以整点为顶点的简单多边形(任两边不交叉),它内部整点数为a,它的边上(包括顶点)的整点数为b,则它的面积S = a+b/2-1
pick定理及其证明
一个结论:对于长a,宽b的整点矩形,它的一条对角线上的整点数为gcd(a,b)-1

lca && rmq 专题

hdoj2586

    选一个根,lca的同时出每个点到根的距离,u,v间的距离是dist[u]+dist[v]-2*dist[anc];

小技巧:

    以前做过这道题,那个时候q[]数组开成int型的,然后开一个保存询问的结构体数组(struct{int u,v,anc;})然后每次回答一个询问,都要遍历一下该询问数组,看看对上哪一个询问,然后写入答案,这样效率不好(每次保存一个询问的答案要O(q),q是询问数)

  其实只需要把q数组开成node类型,node中记录该询问的id,这样每次解答了一个询问就可以O(1)时间写入一个一维数组ans[]。(ans[i]表示第i个询问的答案)

ps:题目中每个case后输出一个空行是骗人的~~~

 

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<vector>
#define maxn 40010
#define maxe 80010
#define maxm 210
using namespace std;
typedef struct Edge{
	int to;
	int w;
	int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int cnt;
int bin[maxn];
bool visit[maxn];
typedef struct node{
	int to;
	int id;
}node;
int ans[maxm],dist[maxn];
vector<node> q[maxn];
void init(int n)
{
	int i;
	dist[0]=dist[1]=0;
	for(i=1;i<=n;i++)
		if(!q[i].empty())
			q[i].clear();
	cnt=0;
	memset(visit,0,sizeof(visit));
	memset(head,-1,sizeof(head));
	return;
}
void add(int a,int b,int w)
{
	edge[cnt].w=w;
	edge[cnt].to=b;
	edge[cnt].next=head[a];
	head[a]=cnt++;
	return;
}
int find(int x)
{
	int r=x;
	while(bin[r]!=r)
		r=bin[r];
	int t=x,tmp;
	while(t!=r)
	{
		tmp=bin[t];
		bin[t]=r;
		t=tmp;
	}
	return r;
}
void merge(int x,int y)
{
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy)
		bin[fx]=fy;
	return;
}
void lca(int cur,int fa,int w)
{
	int i,j;
	dist[cur]=dist[fa]+w;
	bin[cur]=cur;
	visit[cur]=1;
	int d=q[cur].size();
	for(i=0;i<=d-1;i++)
	{
		int v=q[cur][i].to;
		if(visit[v])
		{
			int anc=find(v);
			ans[q[cur][i].id]=dist[cur]+dist[v]-2*dist[anc];
		}
	}
	for(i=head[cur];i!=-1;i=edge[i].next)
	{
		int v=edge[i].to;
		int w=edge[i].w;
		if(visit[v])
			continue;
		lca(v,cur,w);
		merge(v,cur);
	}
	return;
}
int main()
{
	int t;
	int i,j;
	scanf("%d",&t);
	while(t--)
	{
		int n,m;
		int a,b,k;
		scanf("%d%d",&n,&m);
		init(n);
		for(i=1;i<=n-1;i++)
		{
			scanf("%d %d %d",&a,&b,&k);
			add(a,b,k);
			add(b,a,k);
		}
		for(i=1;i<=m;i++)
		{
			int u,v;
			scanf("%d %d",&u,&v);
			node tmp;
			tmp.to=v;tmp.id=i;
			q[u].push_back(tmp);
			tmp.to=u;
			q[v].push_back(tmp);
		}
		lca(1,0,0);
		for(i=1;i<=m;i++)
			printf("%d\n",ans[i]);

	
	}



	//system("pause");
	return 0;
}

hdoj3078
题意:给你一棵树,每个顶点都有一个权值,然后给你两种操作,k a b,k=0的时候表示把a的权值变成b,k>0的时候表示求解a到b的路径上第k大的权值是多少。
朴素的深度比较法求lca即可,求解lca的同时记录途中经过的点的权值,排序一下即可,注意两个点相同时的处理。
粗粗估计一下平均情况时间复杂度:dfs标上深度:O(n),对于每个询问:O(logn+(logn)*(loglogn)),所以复杂度为O(n)-O(q*(logn+(logn)*(loglogn))),计算器算一下最坏情况下大概是4992786次运算(10^6级别),可以过。
如果数据变态,树是一条链,那么复杂度变成O(n)-O(q*(n+nlogn)),大概是10^10数量级的,那就悲催了。。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<vector>
#include<algorithm>
#define maxn 80010
#define maxe 170010
#define maxq 40010
using namespace std;
typedef struct Edge{
	int to;
	int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int lay[maxn];
bool visit[maxn];
int cnt;
int fa[maxn],depth[maxn];
void dfs(int cur,int f,int dep)
{
	fa[cur]=f;
	visit[cur]=1;
	depth[cur]=dep+1;
	for(int i=head[cur];i!=-1;i=edge[i].next)
	{
		int v=edge[i].to;
		if(visit[v]) continue;
		dfs(v,cur,depth[cur