AtCoder Beginner Contest 443 部分题目题解

比赛传送门：AtCoder Beginner Contest 443。

G 题解

先推个式子。

\[\begin{aligned} &\phantom{\iff }\ k < (Ak+B) \bmod M\\ &\iff k+1 \le Ak+B-M\left\lfloor\frac{Ak+B}M \right\rfloor \\ &\iff \left\lfloor\frac{Ak+B}M \right\rfloor \le \frac{(A-1)k+(B-1)}M\\ &\iff \left\lfloor\frac{Ak+B}M \right\rfloor \le \left\lfloor\frac{(A-1)k+(B-1)}M\right\rfloor\\ \end{aligned} \]

容易发现 \(\displaystyle \left\lfloor\frac{Ak+B}M \right\rfloor-\left\lfloor\frac{(A-1)k+(B-1)}M \right\rfloor\) 只能为 \(0\) 或 \(1\)。

那么答案即为 \(\displaystyle N-\sum_{k=0}^{N-1} \left(\left\lfloor\frac{Ak+B}M \right\rfloor-\left\lfloor\frac{(A-1)k+(B-1)}M \right\rfloor\right)\)。

类欧即可。

#include<bits/stdc++.h>
#include<atcoder/math>
#define int long long
#define double long double
using namespace std;
using namespace atcoder;
inline int read(){
	char c=getchar();
	int f=1,ans=0;
	while(c<48||c>57) f=(c==45?f=-1:1),c=getchar();
	while(c>=48&&c<=57) ans=(ans<<1)+(ans<<3)+(c^48),c=getchar();
	return ans*f;
}
main(){
	int T=read();
	while(T--){
		int n=read(),m=read(),a=read(),b=read();
		printf("%lld\n",n-(floor_sum(n,m,a,b)-floor_sum(n,m,a-1,b-1)));
	}
    return 0;
}

F 题解

首先这个东西就是一个 bfs，每个状态记录一下当前的数位和取模的值，然后 bfs 即可，复杂度显然是对的。

#include<bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
inline int read(){
	char c=getchar();
	int f=1,ans=0;
	while(c<48||c>57) f=(c==45?f=-1:1),c=getchar();
	while(c>=48&&c<=57) ans=(ans<<1)+(ans<<3)+(c^48),c=getchar();
	return ans*f;
}
int n;
struct node{
	int x,s;
};
const int N=3e6+10;
int vis[N][10];
#define pii pair<int,int>
pii pre[N][10];
void print(int x,int s){
	if (pre[x][s]==(pii){0,0}) return ;
	print(pre[x][s].first,pre[x][s].second);
	putchar(s+'0');
} 
inline void bfs(){
	queue<node>q;q.push({0,1});
	bool flag=1;
	vis[0][1]=1;
	while(!q.empty()){
		node x=q.front();q.pop();
		if (x.x==0&&!flag){print(0,x.s);return ;}
		flag=0;
		for (int i=x.s;i<=9;i++) if (!vis[(x.x*10+i)%n][i]) vis[(x.x*10+i)%n][i]=1,pre[(x.x*10+i)%n][i]={x.x,x.s},q.push({(x.x*10+i)%n,i});
	} 
	puts("-1");
}
main(){
	n=read();
	if (n==1) return 0&puts("1");
	bfs();
    return 0;
}