|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
本帖最后由 zhangjinxuan 于 2023-1-25 20:14 编辑
上一关:数楼梯
梦想护卫舰 第12期 破译密码
你们走过了楼梯,来到了神庙大门,这门需要密码……
密码门上只有两串数字,而地上有一串文字:
这两串数字位数是相同的,一个是 A, 一个是 B, 有 n 位,1 <= n <= 200000,也是一个合法的十进制数字
现在你可以执行多次这个操作(或者不操作):
选择一个数字 i ,1 <= i <= n,将 A 从左往右数的第 i 位 与 B 从左往右数的第 i 位交换
A * B 得到的最小值就是密码
但这个数可能很大,所以你还要对 998244353 取余
注意:我们要找的是 A * B 的最小值,请不要最小化余数
输入格式
三行,第一行一个整数 n,第二行是 A,第三行是 B
输出格式
一个整数,表示最小值
输入样例1
输出样例1
样例解释1
交换个位(i = 1),A = 12, B = 23, 12 * 23 = 276,这是最小值了,不可能找到更小的
输入样例2
输出样例2
样例解释2
交换个位(i = 1),十位 (i = 2),万位 (i = 5),十万位(i = 6),A = 20000100, B = 21222322,A * B 998244353 = 54558365
注意:该题非原创,来自 ARC154,链接在这里
答案与解析
[/hide]
最佳战士
名字:ba21
奖励:最佳答案+5鱼币5荣誉
其他说明:使用语言为python
[/hide]
下一关: 细胞分裂
本帖最后由 ba21 于 2023-1-24 21:12 编辑
python 的大数相乘使用的是(算法)所以还真不慢。
闲着用弄弄,重在参与:
C代码
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- void getNewNumber(char *a, char *b);
- char *MultipyBigNumber(char *a, char *b);
- long long mod(char *divisor, long long number);
- void swap(char *a, char *b, int i);
- int main()
- {
- char a[] = "51562165415643212316";
- char b[] = "52213412312166548821";
- int number = 998244353;
- getNewNumber(a, b);
- printf("%lld\n", mod(MultipyBigNumber(a,b), number));
- return 0;
- }
- // 获取最小乘积所需要的被乘数和乘数
- void getNewNumber(char *a, char *b)
- {
- int i;
- for (i = 0; i < strlen(a); i++)
- {
- if (a[i] > b[i])
- {
- swap(a, b, i);
- }
- }
- }
- // 大数相乘
- char *MultipyBigNumber(char *a, char *b)
- {
- int i, j, x, bitLeft, bitRight;
- int lenA = strlen(a);
- int lenB = strlen(b);
- int len = lenA + lenB;
- char *arr;
- arr = (char*)malloc(sizeof(char)*(len+1));
- arr[len] = '\0';
- arr = &arr[len];
- lenA--;
- lenB--;
- i = x = 0;
- while(i < len - 1 || x != 0)
- {
- for(j = 0; j <= i; j++)
- {
- bitLeft = lenA - i + j;
- bitRight = lenB - j;
- if(bitLeft >= 0 && bitRight >= 0)
- {
- x += (a[bitLeft] - '0') * (b[bitRight] - '0');
- }
- }
- *(--arr) = x % 10 + '0';
- x /= 10;
- i++;
- }
- if(*arr++ == '0')
- {
- *arr = '\0';
- }
- return --arr;
- }
- // 求余数
- long long mod(char *divisor, long long number)
- {
- long long m=0;
- for(int i=0; i<strlen(divisor); i++){
- m = (m*10+(divisor[i]-'0'))%number;
- }
- return m;
- }
- // 交换
- void swap(char *a, char *b, int i)
- {
- a[i] = a[i]^b[i];
- b[i] = a[i]^b[i];
- a[i] = a[i]^b[i];
- }
复制代码
python代码
- import random
- def getNum(n):
- s = ''
- for i in range(n):
- s+=str(random.randint(0, 9))
- return s
- n = 200000
- a = getNum(n)
- b = getNum(n)
- lstA = list(a)
- lstB = list(b)
- for i in range(n):
- if lstA[i] > lstB[i]:
- lstA[i], lstB[i] = lstB[i], lstA[i]
- newA = int(''.join(lstA))
- newB = int(''.join(lstB))
- print(newA * newB % 998244353)
复制代码
|
|