欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

NOIP 模拟赛 Candy

程序员文章站 2024-03-20 13:30:16
...

MZOJ

很巧妙的一道题,先发现规律
以233为例
233对应的b1…b3分别是:233,332,323,他们的和为888
而888正好是111*(2+3+3)
所以我们对任意一个数都可以写成11...11(i1<=i<=lena[i])11...11*(\sum _{i}^{1<=i<=len}a[i])
而每一个11...1111...11都可以写为(10n1)/9(10^n-1)/9
在求快速幂得答案的时候
x10n19  <==>  9x10n1=>(10n)%9==1x|\frac{10^n-1}{9}\;<==>\;9x|10^n-1 => (10^n)\%9==1
而我们就只需要从小到大枚举每个质数,带入快速幂看看是否合法就可以了

Code

#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(register int (i)=(a);(i)<=(b);(i)++)
#define don(i,a,b) for(register int (i)=(a);(i)>=(b);(i)--)
using namespace std;
const int maxn=6e6+10;
const int maxm=1e3+10;
int a[maxn],vis[maxn],prime[maxn];
char s[maxn];
int len1,cnt,sum;

template <class t> inline void read(t &x) {
	x=0;int f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){x=10*x+ch-'0';ch=getchar();}
	x*=f;
}

void readdata() {
	scanf("%s",s+1);
	len1=strlen(s+1);
	rep(i,1,len1) {
		a[i]=(ll)s[i]-'0';
		sum+=a[i];
	}
}

void get_prime() {
	cnt=0;
	memset(vis,false,sizeof(vis));
	rep(i,2,(5*(1000000))) {
		if(vis[i]==0) {vis[i]=i;prime[++cnt]=i;}
		rep(j,1,cnt) {
			if(prime[j]>vis[i] || prime[j]*i>(5*(1000000))) break;
			vis[prime[j]*i]=prime[j];
		}
	}
}

inline int quickmi(int x,int n,int mod) {
	int ret=1;
	while(n) {
		if(n%2==1) ret=ret*x%mod;
		x=x*x%mod;
		n/=2;
	}
	return ret;//ret表示x^n在模mod后是否为一,为一则可整除
}

void work() {
	get_prime();
	int ans=2;
	rep(i,1,cnt) {
		if(sum%prime[i]==0 || quickmi(10,len1,9*prime[i])==1) {
			ans=prime[i];
			break;
		}
	}
	printf("%d\n",ans);
}

int main() {
	freopen("candy.in","r",stdin);
//	freopen("candy.out","w",stdout);
	readdata();
	work();
	return 0;
}
相关标签: NOIP 模拟赛