沙发

用户名：admin12

访问量：4003

签　名：

看不见我~~看不见我~

等　　级
排　　名	611
经　　验	4161
参赛次数	1
文章发表	5
年　　龄	15
在职情况	学生
学　　校
专　　业

　　自我简介：

小蒟蒻一只，膜拜大佬

TA的其他文章

蓝桥杯算法训练VIP-Car的旅行路线（C++代码）题目样例就是错的，诶~~~
浏览：530

蓝桥杯算法训练VIP-Buying Sets-题解(C++代码)
浏览：483

蓝桥杯2014年第五届真题-矩阵翻硬币（C++代码）
浏览：1412

你可能喜欢

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

蓝桥杯2014年第五届真题-矩阵翻硬币（C++代码）

　　作者: 沙发　　　　发表时间：2020-04-05 18:54:49 浏览：1412　|　评论：2　

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

1. 很容易得出，如果一枚硬币被翻了奇数次，那么它原来的状态肯定是反面朝上，所以，我们要找的就是被翻了奇数次的硬币
1.  根据Q操作定义，我们举个例子，对于（2,3）这个点只有在（1,1）（1,3）（2,1）（2,3）这四个点进行Q操作时才翻转，一共翻转了4次，通过多个例子总结不难看出，（x，y）点再所有点进行完Q操作后翻转的次数为a*b次，其中为x的约数，b为y的约数。因此若想要这个硬币被翻奇数次，a和b必须都得是奇数，即x和y都有奇数个约数。

想到这如果数据量不大就想到了如下算法:
```cpp
#include <iostream>
#include <algorithm>
 
using namespace std;
long long numy(long long n)
{
	if(n==1)
		return 1;
	long num=0;
	for(long long i=2;i<=n/2;i++)
		if(n%i==0)
			num++;
	return num+2;
}
int main()
{
	long long n,m,num=0;
	cin>>n>>m;
	for(long long i=1;i<=n;i++)
		for(long long j=1;j<=m;j++)
			if((numy(i)*numy(j))%2==1)
				num++;
	cout<<num<<endl;
	return 0;
}
```
在这个题中这个算法明显是超时的必须另寻他法
先普及一个数论知识：

完全平方数有奇数个约数。那么什么是完全平方数呢，简单的说就是n^2，n为自然数，也就是0，2，4，9……

那个这个问题是不是就转化成了

输入两个数n，m，设小于等于n的完全平方数的个数是a，小于等于m的完全平方数的个数是b,求a*b。

那么怎么求小于等于n和m完全平方数的个数呢？

再普及一个知识：

小于等于n的完全平方数的个数为[sqrt（n）]个，即为n的平方根向下取整

那么这个题目有转化成了:输入两个数n，m，求[sqrt(n)]*[sqrt(m)]。

这样题目就简单很多了，只要解决两个问题就可以

1.大数的乘法

2.大数的平方根取整

问题1解决方法：

先弄两个代表数值的字符串s1，s2，将s1的每一位与s2相乘，存到一个整形数组里

举个例子s1=“123”，s2=“89”
123x89
![](/image_editor_upload/20200405065918_32085.png)
规律：将s1[i]*s2[j]存入num[i+j+1]中，因为num[0]要存最后进位
存完后，对num数组进行倒着计算

比如27实际上就是123x89计算中3x9=27，即把7留下2进上去
![](/image_editor_upload/20200405070148_11306.png)
最后结果就是10947
问题2解决方法：
假如一个数有偶数位n，那么这个数的方根有n/2位；如果n为奇数，那么方根为（n+1）/2位。

然后，让我们实际看一个例子，我们假设这个数就是1200

1.很明显，它有4位，所以它的方根有2位，然后，我们通过下面的方法来枚举出它的整数根

00*00=0<1200

10*10=100<1200

20*20=400<1200

30*30=900<1200

40*40=1600>1200

所以，这个根的十位就是3，然后，再枚举个位

31*31=961<1200

32*32=1024<1200

33*33=1089<1200

34*34=1156<1200

所以，这个根就是34，因为平方增长的速度还是比较快的，所以速度没有太大问题。为了提高速度，我们可以优化比较函数:

还拿上面的例子来说

30*30=900<1200

40*40=1600>1200

这两个式子，一般来说，我们应该先计算3*3=9，然后在9后面添2个0再与1200比较，但由于数据量很大，添零也会消耗时间
于是我们可以计算需要加的0的数量然后用下面的方法直接比较

1.如果第i个数的平方的位数加上需要添加个零之后位数与原数不相等，那么位数大的数值大

2.如果位数相等就没必要再添零，直接进行字符串比较即可

例如：

30*30=900<1200

40*40=1600>1200

十位是3的时候 3*3=9是1位填上两个零后位数位3位小于1200的4位所以900<1200

十位是4的时候 4*4=16是两位，添上两个零后位数为4位等于1200的四位，所以只需比较字符串16与1200的大小

很明显在字符串中16>1200,所以1600>1200

那么添加零的个数怎么算呢？

假设一个数的平方根取整的位数为n，从前往后算目前计算到了第i位，则需要添加2*（n-1-i）个零

例如：1200 平方根取整有2位，目前算到了第0位（从0开始计数）即30*30(我们算的是3*3)，需要加2*（2-1-0）=2个零
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
string StrMul(string s1,string s2)//大数乘法
{  
    string ans;
	int num[500]={0},i,j;
	for(i=0;i<s1.length();i++)//s计算存到num中
		for(j=0;j<s2.length();j++) 
			num[i+j+1]+=(s1[i]-'0')*(s2[j]-'0');
	for(i=s1.length()+s2.length()-1;i>0;i--)//num的处理	
		if(num[i]>=10)
		{
			num[i-1]+=num[i]/10;
			num[i]%=10;
		}
	for(int i=0;i<=s1.length()+s2.length()-1;i++)//将num数存到ans字串中，注意进位为0的情况
		if(!i&&num[i]||i)
			ans.push_back(num[i]+'0');
	return ans;
}
bool StrCmp(string s1,string s2,int pos)//比较两字符串大小，pos代表应该在s1后面填几个零
{
	if(s1.length()+pos!=s2.length())//如果s1位数不等于s2,
		return s1.length()+pos>s2.length();
	else//位数相等
		return s1>s2;
 } 
string SqrtStr(string s)//大数平方根取整
{
	int len;
	string ans;
	if(s.length()%2==0)//长度为偶数
		len=s.length()/2;
	else
		len=s.length()/2+1;
	for(int i=0;i<len;i++)//一位一位的循环
	{
		ans.push_back('0');
		for(int j=0;j<=9;j++)
		{
			if(StrCmp(StrMul(ans,ans),s,2*(len-1-i)))//需要添加0的个数是2*（len-1-i）解析见上面
				break;
			ans[i]++;
		}
		ans[i]--;
	}
	return ans;
}
int main()
{
	string s1,s2;
	cin>>s1>>s2;
	cout<<StrMul(SqrtStr(s1),SqrtStr(s2))<<endl;
	return 0;
}
```

0.0分

14 人评分

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

　　评论区

司落桉

惊为天人

2022-01-27 20:06:13

牛奶加咖啡

太强了

2021-04-23 17:50:21

沙发

TA的其他文章

你可能喜欢

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

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

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

校门外的树（C++代码）

开心的金明（C++代码）

蓝桥杯2014年第五届真题-矩阵翻硬币（C++代码）

评论区

精彩推荐

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

点我有惊喜！你懂得！

C二级辅导-进制转换（C语言代码）

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

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

WU-输入输出格式练习（C++代码）

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

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

Pascal三角（C语言代码）

简单的事情（C语言代码）

沙发

TA的其他文章

你可能喜欢

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

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

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

校门外的树 （C++代码）

开心的金明 （C++代码）

蓝桥杯2014年第五届真题-矩阵翻硬币 （C++代码）

评论区

精彩推荐

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

点我有惊喜！你懂得！

C二级辅导-进制转换 （C语言代码）

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

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

WU-输入输出格式练习 （C++代码）

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

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

Pascal三角 （C语言代码）

简单的事情 （C语言代码）

校门外的树（C++代码）

开心的金明（C++代码）

蓝桥杯2014年第五届真题-矩阵翻硬币（C++代码）

　　评论区

C二级辅导-进制转换（C语言代码）

WU-输入输出格式练习（C++代码）

Pascal三角（C语言代码）

简单的事情（C语言代码）