题蛮正常的,拿了个rk3,感觉还行。


T1

令所有数位上的数的和为 \(sum\) ,不难发现要求的就是 \(sum\times \frac{10^n-1}{9}\),最小的质因数要么在 \(sum\) 中,要么在 \(\frac{10^n-1}{9}\) 中。在 \(sum\) 中的最小质因数很好求出来,而 \(\frac{10^n-1}{9}\) 的质因数不好求出,但是由于它可能成为答案的质因数只能比 \(sum\) 的最小质因数小,所以可以枚举质数 \(p\) ,判断 \(\frac{10^n-1}{9} \ {\rm mod} \ p\) 是否等于零即可。

判断的时候转换一下:

\[\begin{aligned} \frac{10^n-1}{9} \ {\rm mod} \ p&=0\\ \frac{10^n-1}{9}&=k\times p\\ 10^n&=k\times 9p+1\\ 10^n \ {\rm mod} \ 9p&=1 \end{aligned} \]

快速幂算出 \(10^n \ {\rm mod} \ 9p\) 即可。

\(\text{Code}:\)

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long lxl;
const int maxn=4500005;

template <typename T>
inline void read(T &x)
{
	x=0;T f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	x*=f;
}

int prime[maxn],cnt;
bool flag[maxn];

inline void sieve()
{
	for(int i=2;i<maxn;++i)
	{
		if(!flag[i]) prime[++cnt]=i;
		for(int j=1;j<=cnt&&i*prime[j]<maxn;++j)
		{
			flag[i*prime[j]]=true;
			if(!(i%prime[j])) break;
		}
	}
}

inline lxl fmi(lxl a,lxl b,lxl mod)
{
	lxl res=1;
	a%=mod;
	while(b>0)
	{
		if(b&1) (res*=a)%=mod;
		(a*=a)%=mod;
		b>>=1;
	}
	return res;
}

inline lxl divid(lxl x)
{
	for(int i=1;i<=cnt;++i)
		if(!(x%prime[i]))
			return prime[i];
	return x;
}

inline bool calcu(int bit,lxl mod)
{
	return fmi(10,bit,mod*9)==1;
}

char s[500005];
lxl sum;

int main()
{
//	system("make.exe");
#ifndef ONLINE_JUDGE
	freopen("candy.in","r",stdin);
	// freopen("candy.out","w",stdout);
#endif
	sieve();
	scanf("%s\n",s+1);
	int n=strlen(s+1);
	for(int i=1;i<=n;++i)
		sum+=s[i]-'0';
	lxl x=divid(sum);
	if(sum!=1)
	{
		for(int i=1;i<=cnt&&prime[i]<=sum;++i)
			if(calcu(n,prime[i]))
			{
				x=min(x,1ll*prime[i]);
				break;
			}
	}
	else
	{
		for(int i=1;i<=cnt;++i)
			if(calcu(n,prime[i]))
			{
				x=prime[i];
				break;
			}
	}
	printf("%lld\n",x);
	return 0;
}

T2

区间DP,考场上打了个爆搜跑路。

\(L_{i,j}\) 表示区间 \([i,j]\) 是否能成为 \(j\) 的左子树,\(R_{i,j}\) 表示区间 \([i,j]\) 是否能成为 \(i\) 的右子树。

枚举子树的根 \(k\) 进行转移:

\[\begin{aligned} L_{i,j}&=L'_{i,j}\or (L_{i,k}\and R_{k,j-1}\and [{\rm gcd}(a_j,a_k)\not =1])\\ R_{i,j}&=R'_{i,j}\or (L_{i+1,k}\and R_{k,j}\and [{\rm gcd}(a_i,a_k)\not =1])\\ \end{aligned} \]

时间复杂度 \(O(n^3)\)

\(\text{Code}:\)

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define Rint register int
#define INF 0x3f3f3f3f
typedef long long lxl;
const int maxn=5e2+5;

namespace quick {
#define tp template<typename Type>
    namespace in {
        inline char getc() {
            static char buf[1<<21],*p1=buf,*p2=buf;
            return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
        }
        inline int read(char *s) {
            *s=getc();
            while(isspace(*s)) {*s=getc();if(*s==EOF) return 0;}
            while(!isspace(*s)&&*s!=EOF) {s++;*s=getc();}
            *s='\0'; return 1;
        }
        tp inline int read(Type &x) {
            x=0;bool k=false;char c=getc();
            while(!isdigit(c)) {k|=(c=='-');c=getc();if(c==EOF) return 0;}
            while(isdigit(c)) {x=(x<<1)+(x<<3)+(c^48);c=getc();}
            x*=(k?-1:1); return 1;
        }
        template <typename Type,typename... Args>
        inline int read(Type &t,Args &...args) {
            int res=0;
            res+=read(t);res+=read(args...);
            return res;
        }
    }
    using in::read;
    namespace out {
        char buf[1<<21];int p1=-1;const int p2=(1<<21)-1;
        inline void flush() {
            fwrite(buf,1,p1+1,stdout);
            p1=-1;
        }
        inline void putc(const char &c) {
            if(p1==p2) flush();
            buf[++p1]=c;
        }
        inline void write(char *s) {
            while(*s!='\0') putc(*s),s++;
        }
        tp inline void write(Type x) {
            static char buf[30];int p=-1;
            if(x<0) {putc('-');x=-x;}
            if(x==0) putc('0');
            else for(;x;x/=10) buf[++p]=x%10+48;
            for(;p!=-1;p--) putc(buf[p]);
        }
        inline void write(char c) {putc(c);}
        template <typename Type,typename... Args>
        inline void write(Type t,Args ...args) {
            write(t);write(args...);
        }
    }
    using out::write;
    using out::flush;
    tp inline Type max(const Type a,const Type b) {
        if(a<b) return b;
        return a;
    }
    tp inline Type min(const Type a,const Type b) {
        if(a<b) return a;
        return b;
    }
    tp inline void swap(Type &a,Type &b) {
        a^=b^=a^=b;
    }
    tp inline Type abs(const Type a) {
        return a>=0?a:-a;
    }
#undef tp
}
using namespace quick;

int gcd(int a,int b)
{
	return b ? gcd(b,a%b) : a;
}

bool L[maxn][maxn],R[maxn][maxn],G[maxn][maxn];
int n,a[maxn];

int main()
{
#ifndef ONLINE_JUDGE
	freopen("tree.in","r",stdin);
#endif
	int T;read(T);
	while(T--)
	{
		read(n);
		for(int i=1;i<=n;++i)
		{
			read(a[i]);
			for(int j=i;j<=n;++j)
				L[i][j]=R[i][j]=0;
		}
		for(int i=1;i<=n;++i)
		{
			L[i][i]=R[i][i]=1;
			for(int j=i+1;j<=n;++j)
				G[i][j]=gcd(a[i],a[j])!=1;
		}
		for(int l=2;l<=n;++l)
			for(int i=1;i+l-1<=n;++i)
			{
				int j=i+l-1;
				for(int k=i;k<j;++k)
					if(L[i][j]|=L[i][k]&R[k][j-1]&G[k][j])
						break;
				for(int k=i+1;k<=j;++k)
					if(R[i][j]|=L[i+1][k]&R[k][j]&G[i][k])
						break;
			}
		bool flag=false;
		for(int i=1;i<=n;++i)
			if(L[1][i]&R[i][n])
			{
				flag=true;
				break;
			}
		puts(flag?"Yes":"No");
	}
	return 0;
}

T3

考了原题 LuoguP4211 [LNOI2014]LCA ,大概思路是把深度和转化为链加,查询时查询链和,询问差分一下即可。

\(\text{Code}:\)

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <ctime>
using namespace std;
typedef long long lxl;
const int maxn=1e5+5;
const int mod=201314;

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
template <typename T>
inline void read(T &x)
{
	x=0;T f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	x*=f;
}

struct edge
{
	int u,v,next;
	edge(int u,int v,int next):u(u),v(v),next(next){}
	edge(){}
}e[maxn];

int head[maxn],ecnt;

inline void add(int u,int v)
{
	e[ecnt]=edge(u,v,head[u]);
	head[u]=ecnt++;
}

int n,q;

int dfn[maxn],fa[maxn],dep[maxn];
int top[maxn],son[maxn],siz[maxn],dfs_cnt;

void dfs1(int u)
{
	dep[u]=dep[fa[u]]+1;
	siz[u]=1;
	son[u]=-1;
	for(int i=head[u];~i;i=e[i].next)
	{
		int v=e[i].v;
		dfs1(v);
		siz[u]+=siz[v];
		if(!~son[u]||siz[son[u]]<siz[v]) son[u]=v;
	}
}

void dfs2(int u,int t)
{
	dfn[u]=++dfs_cnt;
	top[u]=t;
	if(!~son[u]) return;
	dfs2(son[u],t);
	for(int i=head[u];~i;i=e[i].next)
	{
		int v=e[i].v;
		if(v==son[u]) continue;
		dfs2(v,v);
	}
}

namespace Segment_Tree
{
	struct node
	{
		int l,r,sum,lazy;
		node(int l,int r,int sum,int lazy=0)
			:l(l),r(r),sum(sum),lazy(lazy){}
		node(){}
	}tree[maxn<<2];
	#define ls (p<<1)
	#define rs (p<<1|1)
	inline void add(int p,int d)
	{
		(tree[p].sum+=(tree[p].r-tree[p].l+1)*d)%=mod;
		(tree[p].lazy+=d)%=mod;
	}
	inline void push_down(int p)
	{
		if(!tree[p].lazy) return;
		add(ls,tree[p].lazy);
		add(rs,tree[p].lazy);
		tree[p].lazy=0;
	}
	inline void update(int p)
	{
		tree[p].sum=(tree[ls].sum+tree[rs].sum)%mod;
	}
	void build(int p,int l,int r)
	{
		tree[p]=node(l,r,0);
		if(l==r) return;
		int mid=(l+r)>>1;
		build(ls,l,mid);
		build(rs,mid+1,r);
	}
	void modify(int p,int L,int R,int d)
	{
		int l=tree[p].l,r=tree[p].r;
		if(L<=l&&r<=R) return add(p,d),void();
		push_down(p);
		int mid=(l+r)>>1;
		if(L<=mid) modify(ls,L,R,d);
		if(R>mid) modify(rs,L,R,d);
		update(p);
	}
	int query(int p,int L,int R)
	{
		int l=tree[p].l,r=tree[p].r;
		if(L<=l&&r<=R) return tree[p].sum;
		push_down(p);
		int mid=(l+r)>>1,ans=0;
		if(L<=mid) (ans+=query(ls,L,R))%=mod;
		if(R>mid) (ans+=query(rs,L,R))%=mod;
		return ans;
	}
}

struct ques
{
	int p,z,id,type;
	ques(int p,int z,int id,int type)
		:p(p),z(z),id(id),type(type){}
	ques(){}
	inline bool operator < (const ques &T)const
	{
		return p<T.p;
	}
}querys[maxn<<1];

int ans[maxn];

inline void modify(int x,int d)
{
	for(;x;x=fa[top[x]])
		Segment_Tree::modify(1,dfn[top[x]],dfn[x],d);
}

inline int query(int x)
{
	int res=0;
	for(;x;x=fa[top[x]])
		(res+=Segment_Tree::query(1,dfn[top[x]],dfn[x]))%=mod;
	return res;
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("elf.in","r",stdin);
	freopen("elf.out","w",stdout);
#endif
	read(n),read(q);
	memset(head,-1,sizeof(head));
	for(int i=2;i<=n;++i)
	{
		read(fa[i]);
		add(fa[i],i);
	}
	dfs1(1);
	dfs2(1,1);
	Segment_Tree::build(1,1,n);
	for(int i=1,l,r,z;i<=q;++i)
	{
		read(l),read(r),read(z);
		querys[i*2-1]=ques(l-1,z,i,-1);
		querys[i*2]=ques(r,z,i,1);
	}
	sort(querys+1,querys+q*2+1);
	for(int i=1,p=0;i<=q*2;++i)
	{
		ques &qu=querys[i];
		while(p<qu.p) modify(++p,1);
		(ans[qu.id]+=mod+qu.type*query(qu.z))%=mod;
	}
	for(int i=1;i<=q;++i)
		printf("%d\n",ans[i]);
	return 0;
}