2012 金华网络赛小记

1001：没看

1002：没看

1003：没看

1006：最水的概率DP，也是我们队最早A的题，1A

1004: 队友敲了半天才发现方法错了，改了后1A

1008：注意到修改和询问的次数比较少，所以可以先利用容斥原理求出给定区间内与p互质的数的和，然后再考虑那些已经被改变的位置

1010：知道怎么求LCA的话，基本上属于模拟题，不过有一些trick，根节点的兄弟有一个，最近公共祖先不能是询问的两个点中的某一个，这道题错的比较惨

去除hdu系统的原因CE了两次，这道题5A。这场比赛我几乎被这道题废了，出题人专门搞trick，有意思么- -

1005：比赛还有半个小时不到，看到这种题肯定就想到有没有模板，于是乎猥琐的google了一下，然后再猥琐的贴模板，然后就A了。。。。

总结：这场比赛几乎没什么思考的时间，题目的质量不是很高吧，模板题、原题出在网络赛真心不太好。

贴几个代码吧

1010

#include<cstdio>#include<map>#include<vector>using namespace std;int gcd(int a,int b){return b?gcd(b,a%b):a;}typedef __int64 lld;vector<int>prime;int nprime[1000]={1,1};void init(){    int i;    int c;    for(i=2;i<1000;++i){        if(!nprime[i]){            prime.push_back(i);            for(c=i+i;c<1000;c+=i)nprime[c]=1;        }    }}lld getsum(int n,int r){    vector<int>p;    int i;    for(i=0;prime[i]*prime[i]<=r;++i){        if(r%prime[i]==0){            p.push_back(prime[i]);            while(r%prime[i]==0){                r/=prime[i];            }        }    }    if(r>1)p.push_back(r);     lld sum=(lld)n*(n+1)/2;    for(int num=1;num<(1<<p.size());++num){        lld mult=1;        int ones=0;        for(i=0;i<p.size();i++){            if(num&(1<<i)){                ones^=1;                mult*=p[i];            }        }        if(ones)sum-=(lld)(n/mult)*(n/mult+1)/2*mult;        else sum+=(lld)(n/mult)*(n/mult+1)/2*mult;    }    return sum;}int main(){    int t;    scanf("%d",&t);    init();    while(t--){        map<int,int>chg;        map<int,int>::iterator it;        int n,m;        scanf("%d%d",&n,&m);        int cmd;        int x,y,c,p;        while(m--){            scanf("%d%d",&cmd,&x);            if(cmd==1){                scanf("%d%d",&y,&p);                lld res=getsum(y,p)-getsum(x-1,p);                for(it=chg.lower_bound(x);it!=chg.end()&&it->first<=y;++it){                    if(gcd(it->first,p)==1)res-=it->first;                    if(gcd(it->second,p)==1)res+=it->second;                }                printf("%I64d\n",res);            }else{                scanf("%d",&c);                chg[x]=c;            }        }    }    return 0;}