Codeforces Round #450 (Div. 2)

A.

弱智题

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,i,j,k,x,y,cnt[2]={0};
    cin>>n;
    for(i=1;i<=n;i++){
        scanf("%d%d",&x,&y);
        if(x<0)cnt[0]++;
        else cnt[1]++;
    }
    if(cnt[0]<=1||cnt[1]<=1){
        puts("Yes");
    }
    else puts("No");

    return 0;
}

B.

首先要知道一个结论:对于$a/b$,他的小数部分的循环节长度不会超过$b$,所以我们只要检查小数点后的最多$b$位就可以知道$c$是否有出现过了。然后关键就是如何求小数点后的位数了。这个可以用长除法来做,具体思想其实就是不断把被除数乘10然后除以除数获得下一位小数位(相当于不断地将小数点右移一位),写写就明白了。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c,i,j,k;
    cin>>a>>b>>c;
    for(i=1;i<=b;i++){
        if(a*10/b==c){
            cout<<i<<endl;return 0;
        }
        a=a*10%b;
    }
    cout<<-1<<endl;

    return 0;
}

C.

其实很容易想到一个贪心的想法,就是从前往后扫一遍,对于每个数,如果前面恰好有一个数大于等于当前数,那么那个数的“删除值”就应该+1,然后找出”删除值“最大的数即可。但是还有一个问题就是每个数同时可能本身也是一个”record”,所以对于每个数,如果他是”record”,那么他的删除值就是1,然后每次找到一个后面的数要删除这个数,那么他的删除值就-1,最后找出删除值最小的数即可(初始删除值都为0)

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>P;
int main()
{
    int n,i,j,k,maxn=0,ans=0,premaxn=0;
    cin>>n;
    int num[100005],pos[100005]={0};
    for(i=1;i<=n;i++){
        scanf("%d",&num[i]);
        if(num[i]>maxn){
            pos[i]=1;
            premaxn=maxn;maxn=num[i];k=i;
        }
        else if(num[i]>premaxn){
            pos[k]--;premaxn=num[i];
        }
    }
    int minn=2;
    for(i=1;i<=n;i++){
        if(pos[i]<minn){
            ans=num[i];minn=pos[i];
        }
        else if(pos[i]==minn){
            ans=min(ans,num[i]);
        }
    }
    cout<<ans<<endl;

    return 0;
}

D.

首先,如果x不能整除y,那么就可以直接滚蛋了。 令$f(t)$表示若干个数和为$t$,$gcd$为1。那么答案就是$f(\frac{y}{x})$. 令$g(t)$表示若干个数和为$t$,那么显然有$g(t)=2^{t-1}$:想象一下,把t分成t个1,那么相邻的1之间分开与否都是不同的(本题的序列是有序的)。 注意到有$g(t)=\sum_{i=1}^{t_i}f(\frac{t}{t_i})$($t_i$是$t$的约数), 所以有$f(t)=g(t)-\sum_{i=2}^{sz}f(\frac{t}{t_i})$. 于是先把y除以x,然后求出y的所有约数,从小到大排序后,从大到小枚举每个约数,对于每个约数,我们可以先算出他的$g(i)$,然后枚举所有比他大的约数,如果某个约数能整除他,那么那个约数对应的$f(i)$就应该被减去。最后输出$f(1)$即可。以及,注意取模的问题,要用快速幂&小心负数。

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
ll mod_pow(ll x,ll y)
{
    ll res=1;
    while(y){
        if(y&1){
            res=res*x%mod;
        }
        y>>=1;x=x*x%mod;
    }
    return res;
}
ll f[100000];
int main()
{
    int x,y,i,j,k;
    cin>>x>>y;
    if(y%x){
        puts("0");return 0;
    }
    y/=x;vector<int>ys;
    for(i=1;i*i<=y;i++){
        if(y%i==0){
            ys.push_back(i);
            if(i*i!=y)
                ys.push_back(y/i);
        }
    }
    sort(ys.begin(),ys.end());
    for(i=ys.size()-1;~i;i--){
        f[i]=mod_pow(2,y/ys[i]-1);
        for(j=ys.size()-1;j>i;j--)
            if(ys[j]%ys[i]==0)
                f[i]=(f[i]-f[j]+mod)%mod;
    }
    cout<<(f[0]+mod)%mod<<endl;

    return 0;
}