- E.Easy Problem
- Description:
- Zghh likes number, but he doesn't like writing problem description. So he will just give you a problem instead of telling a long story for it.
- Now given a positive integer x and k digits a1,a2,...,ak, can you find a positive integer y such that y is the multiple of x and in decimal representation y contains all digits of a1,a2,...,ak.
- Input:
- The first line contains an integer T (1<=T<=10000) which is the number of test case.The following T lines each line is a test case, start with two integer x (1<=x<=1e8) and k (1<=k<=10), k integer a1,a2,..,ak (0<=ai<=9 for i=1..k and ai!=aj for i!=j) is following.
- Output:
For each test case output your answer y. Your answer should be a positive integer without leading zero and should be no more than 1e18. Every answer that satisfy the conditions descripted above will be accepted.
- Sample Input:
- 3
- 5 3 1 5 7
- 21 4 2 5 6 9
- 10 9 0 1 2 3 4 5 6 7 9
- Sample Output:
- 175
- 2592576
- 976543210
题意:
多组数据, 每组数据给出一个数 x, 然后 k 个 0~9 的数, 现在要你求出一个数 y, 满足 y%x=0 并且 y 包含这 k 个数.
题解:
比赛的时候想了半天都没有想到啊... 后来看别人的代码恍然大悟.
注意这里的数据范围, x 只有 1e8, 然后 0~9 一共 10 个数, 所以我们可以选取一个大数比如 1234567890*1e8, 可以将这个作为答案进行待定.
因为要求能够整除, 所以我们用这个大数 (假定为 n)n%x, 令 r=n%x, 那么易知 r 是小于 1e8 的, 我们现在用 n 加上 x-r 那么就可以同时满足题目中的条件了.
这里如果用减的话可能会因为借位而对 1234567890 进行改变, 用加就不用担心这个问题出现了.
感觉思路特别巧妙, 主要还是对数据范围的细心观察.
代码如下:
- #include <bits/stdc++.h>
- typedef long long ll;
- ll n = 123456789000000000;
- int main(){
- ll T,k,t,r;
- ll x;
- scanf("%lld",&T);
- while(T--){
- scanf("%lld %lld",&x,&k);
- for(int i=1;i<=k;i++){
- int tmp;
- scanf("%d",&tmp);
- }
- r = n % x;
- t = x - r;
- printf("%lld\n",n+t);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2911142.html