NOIP 模拟赛 Candy
程序员文章站
2024-03-20 13:30:16
...
MZOJ
很巧妙的一道题,先发现规律
以233为例
233对应的b1…b3分别是:233,332,323,他们的和为888
而888正好是111*(2+3+3)
所以我们对任意一个数都可以写成
而每一个都可以写为
在求快速幂得答案的时候
而我们就只需要从小到大枚举每个质数,带入快速幂看看是否合法就可以了
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;
}
上一篇: Java实现MD5加密
下一篇: [NOIp2016]蚯蚓