admin管理员组文章数量:1590692
Yet Another Multiple Problem
Time Limit: 40000/20000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 6255 Accepted Submission(s): 1451
Problem Description There are tons of problems about integer multiples. Despite the fact that the topic is not original, the content is highly challenging. That’s why we call it “Yet Another Multiple Problem”.
In this problem, you’re asked to solve the following question: Given a positive integer n and m decimal digits, what is the minimal positive multiple of n whose decimal notation does not contain any of the given digits?
Input There are several test cases.
For each test case, there are two lines. The first line contains two integers n and m (1 ≤ n ≤ 104). The second line contains m decimal digits separated by spaces.
Input is terminated by EOF.
Output For each test case, output one line “Case X: Y” where X is the test case number (starting from 1) while Y is the minimal multiple satisfying the above-mentioned conditions or “-1” (without quotation marks) in case there does not exist such a multiple.
Sample Input
2345 3
7 8 9
100 1
0
Sample Output
Case 1: 2345
Case 2: -1
Source 2012 Asia Chengdu Regional Contest 【分析】:
题意给出一个n,和m个数字,求出最小的n的倍数,满足这个数中不含那m个数字中的任何一个。
根据同余模定理,按位取数,BFS维护。
看到这个题第一思路是遍历,其实自己知道会有很多数做不必要的检查。
我们要找的这个数模除n==0。在找的过程中会遇到%n不是0的数,那就标记下来,让已经出现过的余数不再做无谓的检查。
同余模定理讲解:点击打开链接
这个题上用到的关键点是,大数取模。
例如要求141%3的余数,如果这里不是141,是一个很大的数,是无法直接求模的。
这里需要分块求模,就是分解成一位一位的。
(a+b)%c=(a%c+b%c)%c;
(a*b)%c=(a%c*b%c)%c;
具体做法是:
先求 1 % 3 = 1;
然后余数1:(1*10 + 4)% 3 = 2;
然后余数2:(2*10 + 1)% 3 =0;
余数为0 ,即为141%3==0;
根据这个定理,跑BFS,队列维护装每一次的余数,去进行下一次余除。
同时用mod[]记录刚才加上的位数。用pre[]数组记录上一次的余数。
【代码】:
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<queue>
using namespace std;
bool vis[10];
int mod[101010],pre[101010];
int n,m,x;
void print(int v)
{
if(~v){
print(pre[v]);
printf("%d",mod[v]);
}
}
void bfs()
{
queue<int>q;
for(int i=1;i<10;i++)//首位,不能为0
{
if(!vis[i]&&mod[i%n]==-1)
{
mod[i%n]=i;
q.push(i%n);
}
}
while(!q.empty())
{
int u=q.front();q.pop();
//printf("u = %d\n",u);
if(u==0){
print(u);puts("");
return;
}
for(int i=0;i<10;i++)
{
if(vis[i])continue;
x=(u*10+i)%n;
if(mod[x]==-1)//没出现过
{
mod[x]=i;//本次模除加的是i
pre[x]=u;//前一次余数是u
q.push(x);
}
}
}
printf("-1\n");
}
int main()
{
int r=1;
while(cin>>n>>m)
{
memset(mod,-1,sizeof(mod));
memset(pre,-1,sizeof(pre));
memset(vis,0,sizeof(vis));
while(m--){
cin>>x;
vis[x]=1;
}
printf("Case %d: ",r++);
bfs();
}
}
版权声明:本文标题:HDU 4474 同余模定理+BFS 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/xitong/1728085087a1144876.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论