JHwong

用户名：dotcpp0724243

访问量：832

签　名：

等　　级
排　　名	3377
经　　验	1945
参赛次数	11
文章发表	16
年　　龄	0
在职情况	学生
学　　校	宁波大学科学技术学院
专　　业

　　自我简介：

TA的其他文章

1435: 蓝桥杯历届试题-国王的烦恼
浏览：156

1427: 蓝桥杯2013年第四届真题-买不到的数目
浏览：39

2529: NOIP2012-同余方程-了解即可
浏览：34

你可能喜欢

不同单词个数统计（C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （Java代码）

C语言训练-求1+2!+3!+...+N!的和（C++代码）

C语言训练-求PI* （C语言代码）（正确结果竟然是谜一样的3.141591）

printf基础练习2 （C++代码）（受教了，，%#o和%#x的用途）三人行，必有我师，，多看题解会有收获

1450: 蓝桥杯2014年第五届真题-矩阵翻硬币

　　作者: JHwong　　　　发表时间：2024-01-13 17:10:12 浏览：31　|　评论：0　

原题链接：蓝桥杯2014年第五届真题-矩阵翻硬币

# 
```cpp
/* 
 * 题目 1450: 蓝桥杯2014年第五届真题-矩阵翻硬币
 * 10^1000 -> 大整数（vector、string待定）
 * flip问题 - 重要的数学关系 - 状态是二维的 - 仅奇数操作改变
 * 题目操作一个格点可以连带修改其整数倍格点。因此，一个点（n,m）的翻动次数是num(n)*num(m),num(int)表示int的约数个数（含自身）
 * 考虑到结果上都是正，也就是原始状态反面的需要翻转奇数次，根据翻转表达式发现尽可能是 奇数*奇数。
 * 小知识点：在包含自身的情况下，仅有完全平方数是奇数。证明：如果不是完全平方数，根据表达式：a = n/b,即{a，b}成对出现且a!=b。
 * 换句话说，只有点（完全平方数，完全平方数）原始状态是反面。
 * 问题转换为在大小为n*m的格网上有几个这样的点考虑到可以使用乘法原理，x轴完全平方数个数*y轴完全平方数个数 = 答案。
 * 于是再次转化问题，考虑数int中有几个完全平方数。这个答案是[sqrt(int)], []表示向下取整。
 * 证明：y=x^2 < int ==> x < sqrt(int)，那么最大的完全平方数是[sqrt(int)]。
 * 接下来就是大整数开方问题：
 * 1.二分可以 - 问题需要先构造大整数（搜索范围） + 设计整除
 * 2.牛顿迭代法 - 利用 x_{n + 1} = 1/2*(x_{n} + a/(x_{n})) - 除法不好设计 比1还难
 * 3.利用关系，开方位数 偶 = len // 2, 奇 = len // 2 + 1; 然后从高至低确认位数 -- 检测
 * 在三种方法中求解 - 牛顿法难度最高，检测中3的利用关系最为简单，并且3会更快。
 * 选用三作为开放算法
 * 
 * 方便输入输出 - string。
 */
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using std::cin;
using std::cout;
using BigInt = std::string;

BigInt mul(BigInt n1, BigInt n2) {
  BigInt ans;
  int num[500] = { 0 }, i, j;
  for (i = 0; i < n1.length(); i++)
    for (j = 0; j < n2.length(); j++)
      num[i + j + 1] += (n1[i] - '0') * (n2[j] - '0'); // 答案位置要偏移 -- 最高位需要进位

// 进位 + 类型转换
  for (i = n1.length() + n2.length() - 1; i > 0; i--) if (num[i] >= 10)
  {
    num[i - 1] += num[i] / 10;
    num[i] %= 10;
  }
  for (int i = 0; i <= n1.length() + n2.length() - 1; i++) if (!i && num[i] || i)
    ans.push_back(num[i] + '0'); 
 
  return ans;
}

bool BigIntCmpLess(const BigInt& n1, const BigInt& n2, int fill) {
  if (n1.length() + fill != n2.length()) return n1.length() + fill < n2.length(); // 位数不同，比位数
  else return n1 < n2; // 相同，扫描比较 -- 选用string的原因 -- 自带了
}

BigInt num(const BigInt& number) {
  int len = number.length() / 2;
  if (number.length() % 2) ++len;       // 确定位数
  
  // 开始计算
  BigInt ans; 
  for (int i = 0; i < len; ++i) {
	ans.push_back('0');
    for (; BigIntCmpLess(mul(ans, ans), number, 2 * (len - i - 1)); ++ans[i]);
	--ans[i]; // 检查出来的是最小的大于，-1还原
  }

return ans;
}

int main() {
  BigInt n, m;
  cin >> n >> m;
  cout << mul(num(n), num(m));
  return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

JHwong

TA的其他文章

你可能喜欢

不同单词个数统计（C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （Java代码）

C语言训练-求1+2!+3!+...+N!的和（C++代码）

C语言训练-求PI* （C语言代码）（正确结果竟然是谜一样的3.141591）

printf基础练习2 （C++代码）（受教了，，%#o和%#x的用途）三人行，必有我师，，多看题解会有收获

1450: 蓝桥杯2014年第五届真题-矩阵翻硬币

评论区

精彩推荐

2005年春浙江省计算机等级考试二级C 编程题(3)，复杂度最低的方法没有之一！！！！！

简单的a+b （C语言代码）

时间转换（Java代码）

【计算两点间的距离】（C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

WU-蓝桥杯算法提高VIP-企业奖金发放（C++代码）

哥德巴赫曾猜测（C语言代码）

回文数字（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

蚂蚁感冒（C语言代码）

JHwong

TA的其他文章

你可能喜欢

不同单词个数统计 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （Java代码）

C语言训练-求1+2!+3!+...+N!的和 （C++代码）

C语言训练-求PI* （C语言代码）（正确结果竟然是谜一样的3.141591）

printf基础练习2 （C++代码）（受教了，，%#o和%#x的用途）三人行，必有我师，，多看题解会有收获

1450: 蓝桥杯2014年第五届真题-矩阵翻硬币

评论区

精彩推荐

2005年春浙江省计算机等级考试二级C 编程题(3)，复杂度最低的方法没有之一！！！！！

简单的a+b （C语言代码）

时间转换 （Java代码）

【计算两点间的距离】 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

WU-蓝桥杯算法提高VIP-企业奖金发放 （C++代码）

哥德巴赫曾猜测 （C语言代码）

回文数字 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

蚂蚁感冒 （C语言代码）

不同单词个数统计（C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C++代码）

　　评论区

时间转换（Java代码）

【计算两点间的距离】（C语言代码）

WU-蓝桥杯算法提高VIP-企业奖金发放（C++代码）

哥德巴赫曾猜测（C语言代码）

回文数字（C语言代码）

蚂蚁感冒（C语言代码）