Educational Codeforces Round 81 (Rated for Div. 2)

A-Display The Number

题意:
给出0-9所需要的小火柴数量,用小于等于n数量的小火柴搭出最大的数字.
思路:
通过观察可以发现只需考虑1,7的情况.
代码:

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=3e5+20;

int main()
{
    int t;scanf("%d",&t);
    while(t--)
    {
        int n;scanf("%d",&n);
        if(n==3) printf("7\n");
        else
        {
            if(n%2==0) printf("1"),n-=2;
            else printf("7"),n-=3;

            while(n>=2) printf("1"),n-=2;
            printf("\n");
        }
    }
}

B-Infinite Prefixes

题意：
给定一个由0,1组成的字符串t,求由t组成的循环串中cnt0-cnt1=m的前缀串个数,若无穷输出-1.
思路:
用a[i]表示前i个数中cnt0-cnt1.
首先我们可以从无穷入手，我们很容易可以证明此时cnt1=cnt0.我们只需遍历a[i],搜索是否存在a[i]==m即可.如果存在则输出无穷，否则输出0.
然后对于一般情况只需考虑寻找(a[i]-m)/(cnt0-cnt1)*(cnt0-cnt1)==a[i]-m的个数.
注意m==0的时候空串也可以，需要ans++.
代码:

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 3e5+20;

int tot,cnt,a[maxn];
char s[maxn];

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        tot=cnt=0;
        int n,m;scanf("%d%d%s",&n,&m,&s);
        for(int i=0;i<n;i++) 
            if(s[i]=='1') a[++tot]=--cnt;
            else a[++tot]=++cnt;

        int flag=1;
        if(!cnt) 
            for(int i=1;i<=n;i++)
                if(m-a[i]==0)
                    flag=0;
        if(!flag) 
        {
            printf("-1\n");
            continue;
        }
        if(!cnt)
        {
            printf("0\n");
            continue;
        }
        int ans=0;if(!m) ans++;
        for(int i=1;i<=n;i++)
        {
            int k=m-a[i];
            int nt=k/cnt;
            if(nt<0) continue;
            if(nt*cnt==k) ans++;
        }
        printf("%d\n",ans);

    } 
}

C-Obtain The String

题意:
给定字符串s,t.t可以由s的子序列组成,求所需s的个数,若不存在输出-1.
思路:
对于不存在的情况，我们只需判断t中的元素是否都在s中出现.
预处理出s中各个字母的位置，遍历t中的字母,通过upper_bound来O(logn)找出是否存在最早的可行位置，如果不行，cnt++,然后再重新从前往后找.

代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+20;
char s[maxn],t[maxn];
int zm[30][maxn];

int js[28],jt[28];

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        for(int i=0;i<26;i++) zm[i][0]=js[i]=jt[i]=0;

        scanf("%s%s",&s,&t);
        int lens=strlen(s),lent=strlen(t);
        for(int i=0;i<lens;i++) js[s[i]-'a']=1;
        for(int i=0;i<lent;i++) jt[t[i]-'a']=1;
        int flag=0;
        for(int i=0;i<26;i++) if(jt[i]&&(!js[i])) flag=1;
        if(flag) 
        {
            printf("-1\n");
            continue;
        }

        for(int i=0;i<lens;i++) zm[s[i]-'a'][++zm[s[i]-'a'][0]]=i;
        int wei=-1;
        int cnt=1;
        for(int i=0;i<lent;i++)
        {
            int kk=t[i]-'a';
            int cur=upper_bound(zm[kk]+1,zm[kk]+zm[kk][0]+1,wei)-zm[kk];
            if(cur>zm[kk][0]) cnt++,wei=-1,i--;
            else wei=zm[kk][cur];
        }
        printf("%d\n",cnt);
    }
}

D-Same GCDs

题意：
给定a,m，求出有多少个x满足 0≤x<m 且 gcd(a,m)=gcd(a+x,m).
思路：

方法一：欧拉公式

设 $g=gcd(a,m)$ ,则 $gcd(\frac{a+x}{g},\frac{m}{g})=1$
可以得到 $gcd(\frac{a+x}{g}mod\frac{m}{g},\frac{m}{g})=1$
由于 $a+x\in [a,a+m-1]$ ,则 $\frac{a+x}{g}\in[\frac{a}{g},\frac{a+m-1}{g}]$
也就是要找出 $[\frac{a}{g},\frac{a+m-1}{g}]$ 中与 $\frac{m}{g}$ 互质的数
根据 $gcd(\frac{a+x}{g}mod\frac{m}{g},\frac{m}{g})=1$ 的性质，我们可以发现等价于找出 $[0,\frac{m-1}{g}]$ 中与 $\frac{m}{g}$ 互质的数
这样我们就可以用欧拉函数来求出我们所要的答案，也就是 $\psi(\frac{m}{gcd(a,m)})$

方法二：容斥

由题意可得我们所要求的是 $[\frac{a}{gcd(a,m)},\frac{a+m}{gcd(a,m)}-1]$ 中与m互质的个数
那么子问题就是求 $[1,k]$ 中与m互质的个数，这样我们就可以通过找m的质数prime[],再运用容斥定理得出答案
代码1：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=3e5+20;

ll getphi(ll x){
      ll i,j,k,res=x;
      for(ll i=2;i*i<=x;i++){
          if(x%i==0)res=res/i*(i-1);
          while(x%i==0)x/=i;
      }
      if(x>1)res=res/x*(x-1);
      return res;
}

int main()
{
    int t;scanf("%d",&t);
    while(t--)
    {
        ll a,m;scanf("%lld%lld",&a,&m);
        ll ans=getphi(m/__gcd(a,m));
        printf("%lld\n",ans);
    }
}

代码2:

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=1000;
ll prime[maxn],tot,a,m,k;

ll f(ll x)
{
    ll ans=0;
    for(int i=1;i<=(1<<tot)-1;i++)
    {
        ll cur=1,cnt=0;
        for(int j=0;j<tot;j++)
        {
            if((i>>j)&1) cur*=prime[j+1],cnt++;
        }
        if(cnt%2) ans+=x/cur;
        else ans-=x/cur;
    }
    return x-ans;
}

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        tot=0;
        scanf("%lld%lld",&a,&m);
        k=__gcd(a,m);a/=k;m/=k;
        ll ddd=m;
        for(ll i=2;i*i<=m;i++)
        {
            if(ddd%i==0) prime[++tot]=i;
            while(ddd%i==0) ddd/=i; 
        }
        if(ddd!=1)prime[++tot]=ddd;
        printf("%lld\n",f(a+m-1)-f(a-1));
    }
}