头像

垫底抽风

让我试试组织能不能用**Markdown**或$$LaTeX$$


访客:10614

离线:2小时前


新鲜事 原文

心疼键盘QAQ shift:我裂开了
图片


活动打卡代码 AcWing 2240. 餐饮

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

const int INF=0x3fffffff;
const int N=405,M=40605;

int n,S,T;
int h[N],e[M],ne[M],w[M],idx=1;
int d[N],cur[N],q[N],hh,tt;

void add(int a,int b,int c)
{
    e[++idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx;
}

bool bfs()
{
    memset(d,0,sizeof d);
    d[S]=1,cur[S]=h[S];
    *q=S,hh=tt=0;
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];i;i=ne[i])
            if(!d[e[i]]&&w[i])
            {
                d[e[i]]=d[t]+1;
                cur[e[i]]=h[e[i]];
                if(e[i]==T)return true;
                q[++tt]=e[i];
            }
    }
    return false;
}

int find(int u,int limit)
{
    if(u==T)return limit;
    int flow=0;
    for(int i=cur[u];i&&flow<limit;i=ne[i])
    {
        cur[u]=i;
        if(d[e[i]]==d[u]+1&&w[i])
        {
            int t=find(e[i],min(w[i],limit-flow));
            if(!t)d[e[i]]=0;
            w[i]-=t,w[i^1]+=t,flow+=t;
        }
    }
    return flow;
}

int dinic()
{
    int maxflow=0,flow;
    while(bfs())while(flow=find(S,INF))maxflow+=flow;
    return maxflow;
}

int main()
{
    int F,D;
    scanf("%d%d%d",&n,&F,&D);
    S=n+n+F+D+1,T=S+1;
    for(int i=1;i<=n;i++)
    {
        add(i,n+i,1);
        add(n+i,i,0);
        int fi,di;
        scanf("%d%d",&fi,&di);
        for(int t;fi--;)
        {
            scanf("%d",&t);
            t+=n+n;
            add(t,i,1);
            add(i,t,0);
        }
        for(int t;di--;)
        {
            scanf("%d",&t);
            t+=n+n+F;
            add(n+i,t,1);
            add(t,n+i,0);
        }
    }
    for(int i=1,j=n+n+1;i<=F;i++,j++)
        add(S,j,1),add(j,S,0);
    for(int i=1,j=n+n+F+1;i<=D;i++,j++)
        add(j,T,1),add(T,j,0);
    printf("%d\n",dinic());
    return 0;
}




#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N=505;
const int M=10005;
const int INF=0x3fffffff;

int n,m,S,T,ans;
int h[N],e[M],w[M],ne[M],idx=1;
int d[N],cur[N],q[N],hh,tt;
bool vis_s[N],vis_t[N];

void add(int a,int b,int c)
{
    e[++idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx;
}

bool bfs()
{
    memset(d,0,sizeof d);
    d[S]=1,cur[S]=h[S];
    *q=S,hh=tt=0;
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];i;i=ne[i])
            if(!d[e[i]]&&w[i])
            {
                d[e[i]]=d[t]+1;
                cur[e[i]]=h[e[i]];
                if(e[i]==T)return true;
                q[++tt]=e[i];
            }
    }
    return false;
}

int find(int u,int limit)
{
    if(u==T)return limit;
    int flow=0;
    for(int i=cur[u];i&&flow<limit;i=ne[i])
    {
        cur[u]=i;
        if(d[e[i]]==d[u]+1&&w[i])
        {
            int t=find(e[i],min(w[i],limit-flow));
            if(!t)d[e[i]]=0;
            w[i]-=t,w[i^1]+=t,flow+=t;
        }
    }
    return flow;
}

void dfs(int u,int type,bool vis[])
{
    vis[u]=true;
    for(int i=h[u];i;i=ne[i])
        if(!vis[e[i]]&&w[i^type])
            dfs(e[i],type,vis);
}

int main()
{
    scanf("%d%d",&n,&m);
    S=0,T=n-1;
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c),add(b,a,0);
    }
    while(bfs())while(find(S,INF));
    dfs(S,0,vis_s),dfs(T,1,vis_t);
    for(int i=0;i<n;i++)
        if(vis_s[i])
            for(int j=h[i];j;j=ne[j])
                if(!(j&1)&&vis_t[e[j]])
                    ans++;
    printf("%d\n",ans);
    return 0;
}


活动打卡代码 AcWing 2234. 多源汇最大流

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N=10005;
const int M=220005;
const int INF=0x3fffffff;

int n,m,S,T;
int h[N],e[M],w[M],ne[M],idx=1;
int d[N],cur[N],q[N],hh,tt;

void add(int a,int b,int c)
{
    e[++idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx;
}

bool bfs()
{
    memset(d,0,sizeof d);
    d[S]=1,cur[S]=h[S];
    *q=S,hh=tt=0;
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];i;i=ne[i])
            if(!d[e[i]]&&w[i])
            {
                d[e[i]]=d[t]+1;
                cur[e[i]]=h[e[i]];
                if(e[i]==T)return true;
                q[++tt]=e[i];
            }
    }
    return false;
}

int find(int u,int limit)
{
    if(u==T)return limit;
    int flow=0;
    for(int i=cur[u];i&&flow<limit;i=ne[i])
    {
        cur[u]=i;
        if(d[e[i]]==d[u]+1&&w[i])
        {
            int t=find(e[i],min(w[i],limit-flow));
            if(!t)d[e[i]]=0;
            w[i]-=t,w[i^1]+=t,flow+=t;
        }
    }
    return flow;
}

int dinic()
{
    int maxflow=0,flow;
    while(bfs())while(flow=find(S,INF))maxflow+=flow;
    return maxflow;
}

int main()
{
    int sc,tc;
    scanf("%d%d%d%d",&n,&m,&sc,&tc);
    S=0,T=n+1;
    for(int x;sc--;)
    {
        scanf("%d",&x);
        add(S,x,INF);
        add(x,S,0);
    }
    for(int x;tc--;)
    {
        scanf("%d",&x);
        add(x,T,INF);
        add(T,x,0);
    }
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c),add(b,a,0);
    }
    printf("%d\n",dinic());
    return 0;
}



#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N=50005;
const int M=350015;
const int INF=0x3ffffff;

int n,m,S,T,sum;
int h[N],e[M],w[M],ne[M],idx=1;
int d[N],cur[N],A[N];
int q[N],hh,tt;

void add(int a,int b,int c)
{
    e[++idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx;
}

bool bfs()
{
    memset(d,0,sizeof d);
    d[S]=1,cur[S]=h[S];
    *q=S,hh=tt=0;
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];i;i=ne[i])
            if(!d[e[i]]&&w[i])
            {
                d[e[i]]=d[t]+1;
                cur[e[i]]=h[e[i]];
                if(e[i]==T)return true;
                q[++tt]=e[i];
            }
    }
    return false;
}

int find(int u,int limit)
{
    if(u==T)return limit;
    int flow=0;
    for(int i=cur[u];i&&flow<limit;i=ne[i])
    {
        cur[u]=i;
        if(d[e[i]]==d[u]+1&&w[i])
        {
            int t=find(e[i],min(w[i],limit-flow));
            if(!t)d[e[i]]=0;
            w[i]-=t,w[i^1]+=t,flow+=t;
        }
    }
    return flow;
}

int dinic()
{
    int maxflow=0,flow;
    while(bfs())while(flow=find(S,INF))maxflow+=flow;
    return maxflow;
}

int main()
{
    int s,t;
    scanf("%d%d%d%d",&n,&m,&s,&t);
    S=0,T=n+1;
    for(int i=1;i<=m;i++)
    {
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        add(a,b,d-c),add(b,a,0);
        A[a]-=c,A[b]+=c;
    }
    for(int i=1;i<=n;i++)
        if(A[i]>0)add(S,i,A[i]),add(i,S,0),sum+=A[i];
        else if(A[i]<0)add(i,T,-A[i]),add(T,i,0);
    add(t,s,INF),add(s,t,0);
    if(dinic()!=sum)puts("No Solution");
    else
    {
        int flow=w[idx];
        w[idx]=w[idx-1]=0;
        S=t,T=s;
        printf("%d\n",flow-dinic());
    }
    return 0;
}



#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N=205;
const int M=20405;
const int INF=0x3fffffff;

int n,m,S,T,sum;
int h[N],e[M],w[M],ne[M],idx=1;
int d[N],cur[N],A[N];
int q[N],hh,tt;

void add(int a,int b,int c)
{
    e[++idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx;
}

bool bfs()
{
    memset(d,0,sizeof d);
    d[S]=1,cur[S]=h[S];
    *q=S,hh=tt=0;
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];i;i=ne[i])
            if(!d[e[i]]&&w[i])
            {
                d[e[i]]=d[t]+1;
                cur[e[i]]=h[e[i]];
                if(e[i]==T)return true;
                q[++tt]=e[i];
            }
    }
    return false;
}

int find(int u,int limit)
{
    if(u==T)return limit;
    int flow=0;
    for(int i=cur[u];i&&flow<limit;i=ne[i])
    {
        cur[u]=i;
        if(d[e[i]]==d[u]+1&&w[i])
        {
            int t=find(e[i],min(w[i],limit-flow));
            if(!t)d[e[i]]=0;
            w[i]-=t,w[i^1]+=t,flow+=t;
        }
    }
    return flow;
}

int dinic()
{
    int maxflow=0,flow;
    while(bfs())while(flow=find(S,INF))maxflow+=flow;
    return maxflow;
}

int main()
{
    int s,t;
    scanf("%d%d%d%d",&n,&m,&s,&t);
    S=0,T=n+1;
    for(int i=0;i<m;i++)
    {
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        add(a,b,d-c),add(b,a,0);
        A[a]-=c,A[b]+=c;
    }
    for(int i=1;i<=n;i++)
        if(A[i]>0)add(S,i,A[i]),add(i,S,0),sum+=A[i];
        else if(A[i]<0)add(i,T,-A[i]),add(T,i,0);
    add(t,s,INF),add(s,t,0);
    if(dinic()!=sum)puts("No Solution");
    else
    {
        int flow=w[idx];
        w[idx]=w[idx-1]=0;
        S=s,T=t;
        printf("%d\n",flow+dinic());
    }
    return 0;
}


活动打卡代码 AcWing 2237. 猪

#include <cstring>

const int INF=0x3fffffff;
const int N=1105;
const int M=202205;

int n,S,T;
int h[N],e[M],w[M],ne[M],idx=1;
int d[N],cur[N],q[N],hh,tt;
char st[105][126],p[126];

void add(int a,int b,int c)
{
    e[++idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx;
}

bool bfs()
{
    memset(d,0,sizeof d);
    d[S]=1,cur[S]=h[S];
    *q=S,hh=tt=0;
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];i;i=ne[i])
            if(!d[e[i]]&&w[i])
            {
                d[e[i]]=d[t]+1;
                cur[e[i]]=h[e[i]];
                if(e[i]==T)return true;
                q[++tt]=e[i];
            }
    }
    return false;
}

int find(int u,int limit)
{
    if(u==T)return limit;
    int flow=0;
    for(int i=cur[u];i;i=ne[i])
    {
        cur[u]=i;
        if(d[e[i]]==d[u]+1&&w[i])
        {
            int t=find(e[i],min(w[i],limit-flow));
            if(!t)d[e[i]]=0;
            w[i]-=t,w[i^1]+=t,flow+=t;
        }
    }
    return flow;
}

int dinic()
{
    int maxflow=0,flow;
    while(bfs())while(flow=find(S,INF))maxflow+=flow;
    return maxflow;
}

int main()
{
    int n1,n2;
    scanf("%d%d",&n2,&n1);
    S=n1+n2+1,T=n=S+1;
    for(int i=1,x;i<=n2;++i)
    {
        scanf("%d",&x);
        add(n1+i,T,x);
        add(T,n1+i,x);
    }
    for(int i=1;i<=n1;i++)
    {
        int A,x;
        for(scanf("%d",&A);A--;)
        {
            scanf("%d",&x);
            st[i][x>>3]|=1<<(x&7);
        }
        memcpy(p,st[i],sizeof p);
        for(int j=i-1;j;j--)
        {
            bool judge=false;
            for(int k=1;k<=n2;k++)
                if((p[k>>3]>>(k&7)&1)&&(st[j][k>>3]>>(k&7)&1))
                {
                    judge=true;
                    break;
                }
            if(judge)
                for(int k=1;k<=n2;k++)
                    if(st[j][k>>3]>>(k&7)&1)
                        p[k>>3]|=1<<(k&7);
        }
        for(int j=1;j<=n2;j++)
            if(p[j>>3]>>(j&7)&1)
            {
                add(i,n1+j,INF);
                add(n1+j,i,0);
            }
        scanf("%d",&x);
        add(S,i,x),add(i,S,0);
    }
    printf("%d\n",dinic());
    return 0;
}




题目描述 $\text{(Problem Statement)}$

祭坛供奉从左到右排成一排的 $N$ 个石头。
从左边数第 $i\ (1 \leq i \leq N)$ 个石头的颜色以字母 $c _ i$ 的形式给出:R表示红色 $\text{(Red)}$,W表示白色 $\text{(White)}$。

你每次只能执行以下两种操作

  • 选择两个石头(不一定要是相邻的)并将二者交换
  • 选择一个石头并改变其颜色(从红色变成白色或者从白色变成红色)

算命者说,一块白色的石头放在一块相邻的红色石头的左边会带来灾难。
至少需要多少次操作,可以到达一个没有这样的白色石头的情况?

约定 $\text{(Constraints)}$

  • $2 \leq N \leq 200000$
  • $c _ i$ 是 RW

输入 $\text{(Input)}$

输入按以下形式的标准输入给出

N
c1 c2 ... cN

输出 $\text{(Output)}$

输出一个整数表示最少需要的操作不熟

输入样例1 $\text{(Sample Input 1)}$

4
WWRR

输出样例1 $\text{(Sample Output 1)}$

2

输入样例2 $\text{(Sample Input 2)}$

2
RR

输出样例2 $\text{(Sample Output 2)}$

0

输入样例3 $\text{(Sample Input 3)}$

8
WRWWRWRR

输出样例3 $\text{(Sample Output 3)}$

3

算法1

(双指针,遍历,枚举) $O(n)$
  • 结论:存在一组最优解,其操作序列中不存在操作$2$
  • 证明:反证法,假设不存在一组操作序列中不存在操作$2$的最优解,
    即每一组最优解的操作序列中,都存在操作$2$
    先将每个操作序列按操作的位置从小到大
    那么对于其中一组最优解,找到第一个为 $1$ 的操作
    对于这个操作,有两种可能,分类讨论
    • 将某个石头由白色变为红色
      执行这个操作,说明这个白色石头的右边必然有至少一个红色石头(如果没有,这个操作可以不做)
      那么就可以将这个操作序列中这步,改为将这个白色石头与其右边的红色石头交换
    • 将某个石头有红色变为白色
      同理,其左边至少有一个白色石头,可以将这步改为交换
  • 那么我们就得到了一个只由交换操作构成的序列

所以我们只需要双指针跑一下,具体:
初始时,第一个指针在最左边,第二个指针在最右边
循环:
第一个指针向右跑,找白色石头;第二个指针向左跑,找红色石头
如果都找到后,第一个指针在第二个指针左边,则交换这两个石头
直到第一个指针跑到第二个指针右边,跳出循环
(和快速排序里的代码几乎是一样的)

时间复杂度

两个指针,
最坏情况下,每个指针会将整个序列遍历一遍
故时间复杂度为 $O(2n) = O(n)$

C++ 代码

#include <cstdio>
#include <cstring>

// n 为序列长度,cnt 为操作数量,str 为读入的序列
int n, cnt;
char str[200005];

int main()
{
    scanf("%d\n%s", &n, str);
    // 这里第一个指针指向最左边的左边,第二个指针指向最右边的右边,会好写一些
    int i = -1, j = n;
    while (i < j)
    {
        while ( ++ i < j && str[i] != 'W'); // 当 i ++ 后在 j 左边,且没找到 'W',则继续循环
        while ( -- j > i && str[j] != 'R'); // 当 j -- 后在 i 右边,且没找到 'R',则继续循环
        if (i < j) cnt ++ ;                 // 如果都找到后 i < j,则 交换次数 ++ ,
        // 这行空出来是用来补充上一行注释的 // 这里并不需要真正地维护操作,只需要记录操作数量即可。
    }
    printf("%d\n", cnt);
    return 0;
}

$$ $$




时间限制$\text{: 2s / }$空间限制$\text{: 1024MB}$
分数:$400$ 分

题目描述 $\text{(Problem Statement)}$

$\text{Takahashi}$ 喜欢 $K$ 的倍数的数

在序列 $7, 77, 777, \ldots$ 这个序列中,第一个是 $K$ 的倍数的数是序列中的第几个?

如果该序列中不存在任何是 $K$ 的倍数的数,请输出 -1

约定 $\text{(Constraints)}$

  • $1 \leq K \leq 10 ^ 6$
  • $K$ 是一个整数

输入 $\text{(Input)}$

输入按如下形式的标准输入给出

K

输出 $\text{(Output)}$

输出一个整数,表示序列中第一个是 $K$ 的倍数的数的位置

输入样例1 $\text{(Sample Input 1)}$

101

输出样例1 $\text{(Sample Output 1)}$

2

输入样例2 $\text{(Sample Input 2)}$

-1

输出样例2 $\text{(Sample Output 2)}$

999983

输入样例3 $\text{(Sample Input 3)}$

999982

输出样例3 $\text{(Sample Output 3)}$


我太菜了,写题都不看数据范围。。后来才知道能 $O(K)$ 爆过去
看到这题,就以为数据范围是 $2 \times 10 ^ 9$,然后调半天 $O(\sqrt K \log K)$ 的程序,还 $\color{red}{WA}$ 了一次。。
这里给出两种解题方法与代码

算法1

(暴力枚举) $O(K)$

推式子题

首先 $7, 77, 777, \ldots$ 这种“字符串”数字不是很好处理,要先把它转化为一般的式子

考虑该序列第 $i$ 项,即
$\overbrace{77 \ldots 7} ^ \text{i 个}$

将其写成一堆数的和的形式,得到
$7 + 70 + \ldots + 7 \times 10 ^ {i - 1} = \sum _ {i = 0} ^ {n - 1} 7 \times 10 ^ i$
(抽象思维能力不好的同学,可以看等式左边这一项)

将因数 $7$ 提出,得到
$7 (1 + 10 + \ldots + 10 ^ {i - 1}) = 7 \times \sum _ {i = 0} ^ {n - 1} 10 ^ i$

根据等比数列求和公式,得到
$7 \times {\large \frac {10 ^ i - 1} {10 - 1}} = {\large \frac 7 9} (10 ^ i - 1)$

也就是说,我们要找到一个最小的 $i$,使得 $K | {\large \frac 7 9} (10 ^ i - 1)$
也就是 $9 K | 7 (10 ^ i - 1)$

设 $d = \gcd(9 K, 7)$
$\because \gcd(9, 7) = 1$
$\therefore d = \gcd(K, 7)$

原式两边可以同时除以 $d$,得到
$9 \times {\large \frac K d | \frac 7 d} (10 ^ i - 1)$(由于 $d$ 是左边和 $7$ 的最大公因数,所以一定可以整除)

右边的 $\large \frac 7 d$ 和左边一定没有公因数(否则不符合 $\small d = \gcd(9 K, 7)$),所以可以将其去掉,得到
$9 \times {\large \frac K d} | (10 ^ i - 1)$

左边是一个常数,设 $c = 9 \times {\large \frac K d}$,那么我们要求的就是
$10 ^ i - 1 \equiv 0 \quad (\text{mod}\ c)$

$\Rightarrow 10 ^ i \equiv 1 \quad (\text{mod}\ c)$

这个就是我们平常常见的形式了

那么根据欧拉定理当 $10 ^ i$ 与 $c$ 互质时,有
$10 ^ {\varphi(c)} \equiv 1 \quad (\text{mod}\ c)$

所以 $\varphi(c)$ 是一个答案,但是,它并不一定是我们所求的最小答案

我们需要从 $1 \sim \varphi(c)$ 枚举一遍,同时维护数列中第 $i$ 个数 $\text{mod}\ c$ 的结果
如果某个数 $\text{mod}\ c$ 为 $0$,则直接输出该数,否则输出-1(当然也可以特判答案为 -1 的情况)

时间复杂度

这里的代码并不是只枚举到 $\varphi(c)$ 的(我偷个懒,给个比较简短的代码)而是直接暴力枚举到 $9 K$ 的,
由于,当 $10 ^ i$ 与 $c$ 互质时,$10 ^ {\varphi(c)} \equiv 1 \quad (\text{mod}\ c)$,所以我们的答案最多会是 $\varphi(c)$
又因为 $\varphi(c) < c = 9 {\large \frac K {\gcd(K, 7)}} < 9 K$,所以我们在枚举到 $9K$ 之前,一定会找到一个答案(否则无解)
循环从 $1 \sim 9 K$ 枚举一遍,时间复杂度为 $O(K)$

C ++ 代码

#include <cstdio>

int main()
{
    int k;
    scanf("%d", &k);
    // i 为当前枚举到了序列中第几个数,p 为当前枚举的数 mod k 的结果
    for (int i = 1, p = 7; i < 9 * k; i ++ , p = (10 * p + 7) % k)
        if (p % k == 0) // 注意这里不能直接写 !p,因为有可能 k == 7,那么第一次就会不输出
        {               // 如果特判了 k == 7 的情况,或者是一开始让 p = 7 % k,那么这里可以直接写 !p
            printf("%d\n", i);
            return 0;
        }
    puts("-1"); // 无解输出 -1
    return 0;
}

算法2(算法1优化)

(不那么暴力的枚举) $O(\sqrt K \log K)$

这里先给出结论,再证明(下面所有字母含义与 算法1 中相同)

  • 结论:如果存在答案,设答案为 $ans$,则 $ans|\varphi(c)$
  • 证明:反证法,假设 $ans \nmid \varphi(c)$
    那么就可以令 $\varphi(c) = k \times ans + r$,其中 $0 < r < ans$
    由于 $ans$ 是一个合法解,所以 $10 ^ {ans} \equiv 1 \quad (\text{mod}\ c)$
    两边同时 $k$ 次方,得 $10 ^ {k \times ans} \equiv 1 \quad (\text{mod}\ c)$
    由于 $\varphi(c)$ 是一个合法解,所以 $10 ^ {\varphi(c)} \equiv 1 \quad (\text{mod}\ c)$
    $\Rightarrow 10 ^ {k \times ans + r} \equiv 1 \quad (\text{mod}\ c)$
    又因为 $10 ^ {k \times ans} \equiv 1 \quad (\text{mod}\ c)$,所以可以两边同时 $\div 10 ^ {k \times ans}$
    得到 $10 ^ r \equiv 1 \quad (\text{mod}\ c)$,所以 $r$ 也是一个合法解
    由于 $0 < r < ans$,不满足 $ans$ 是最小的合法解
    所以假设不成立,原命题证毕

所以,我们只需要先求出 $\varphi(c)$,然后再枚举 $\varphi(c)$ 的所有约数,判断每个约数是否为合法解即可

时间复杂度

首先 $\varphi(c)$ 是可以 $O(\sqrt c)$ 求出来的,板子题在这里
然后枚举 $\varphi(c)$ 的所有约数,时间复杂度为 $O(\sqrt {\varphi(c)})$ 的,板子题在这里
判断每个约数是否合法(即判断 $10 ^ i \text{ mod } c$ 是否为 $1$),时间复杂度为 $O(\log \sqrt {\varphi(c)})$,需要用快速幂,板子题在这里
那么总的时间复杂度即为 $O(\sqrt c + \sqrt {\varphi(c)} \log \sqrt {\varphi(c)})$
因为最坏情况下 $\varphi(c)$ 和 $c$ 是一个级别的,所以时间复杂度可化简为 $O(\sqrt c \log \sqrt c)$
上面已经证明了 $c < 9K$,也就是说,$c$ 和 $K$ 是一个级别的
所以时间复杂度可化简为 $O(\sqrt K \log \sqrt K) = O(\sqrt K \log (K ^ \frac 1 2)) = O(\frac 1 2 \sqrt K \log K) = O(\sqrt K \log K)$

C++ 代码

#include <cstdio>

const int INF=0x3fffffff;

// n 即为 K
int n;

int min(int a, int b)
{
    return a < b ? a : b;
}

// 欧拉函数的板子,返回 phi(x)
int get_phi(int x)
{
    int res = x;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res -= res / i;
            while (x % i == 0) x /= i;
        }
    if (x > 1) res -= res / x;
    return res;
}

// 快速幂板子,求 10 的 k 次方模 mod 的结果
int qmi(int k, int mod)
{
    int res = 1, a = 10;
    while (k)
    {
        // mod 即 c,最大是 n * 9 = 9e6,乘法就可能会爆 int,要转 long long 
        if (k & 1) res = res * 1ll * a % mod;
        a = a * 1ll * a % mod;
        k >>= 1;
    }
    return res;
}

int main()
{
    scanf("%d", &n);
    // 让 n 变成 c
    if (n % 7 == 0) n /= 7; // 由于 7 是质数,所以这里不用再求一遍最大公约数,直接判断是否有因子 7 即可
    n *= 9;
    // phi 存 phi(c) 的值。res 记录答案,初始化为正无穷
    int phi = get_phi(n), res = INF;
    for (int i = 1; i <= phi / i; i ++ )
        if (phi % i == 0) // 如果 i 是 phi 的因子,那么分别判断 i 和 phi / i 是否是合法解,如果是,则更新答案
            if (qmi(i, n) == 1) res = min(res, i); // 由于 i <= phi / i,所以如果 i 是合法解,就不用再判断 phi / i 了
            else if (qmi(phi / i, n) == 1) res = min(res, phi / i);
    printf("%d\n", res == INF ? -1 : res); // 如果 res == INF,说明无解,输出 -1,否则输出 res
    return 0;
}

$$ $$




int main()
{
    void qwq();
    return 0;
}

为什么这段代码可以过编译呀?

main里面还能void一个函数嘛?

可以在main里面调用qwq嘛?如何调用呢?