c/c++算法问题 矩阵翻硬币问题描述 小明先把硬币摆成了一个 n 行 m 列的矩阵。 随后，小明对每一个硬币分别进
c/c++算法问题 矩阵翻硬币
问题描述
小明先把硬币摆成了一个 n 行 m 列的矩阵。
随后，小明对每一个硬币分别进行一次 Q 操作。
对第x行第y列的硬币进行 Q 操作的定义：将所有第 i*x 行，第 j*y 列的硬币进行翻转。
其中i和j为任意使操作可行的正整数，行号和列号都是从1开始。
当小明对所有硬币都进行了一次 Q 操作后，他发现了一个奇迹——所有硬币均为正面朝上。
小明想知道最开始有多少枚硬币是反面朝上的。于是，他向他的好朋友小M寻求帮助。
聪明的小M告诉小明，只需要对所有硬币再进行一次Q操作，即可恢复到最开始的状态。然而小明很懒，不愿意照做。于是小明希望你给出他更好的方法。帮他计算出答案。
输入格式
输入数据包含一行，两个正整数 n m，含义见题目描述。
输出格式
输出一个正整数，表示最开始有多少枚硬币是反面朝上的。
样例输入
2 3
样例输出
1
数据规模和约定
对于10%的数据，n、m
问题描述
小明先把硬币摆成了一个 n 行 m 列的矩阵。
随后，小明对每一个硬币分别进行一次 Q 操作。
对第x行第y列的硬币进行 Q 操作的定义：将所有第 i*x 行，第 j*y 列的硬币进行翻转。
其中i和j为任意使操作可行的正整数，行号和列号都是从1开始。
当小明对所有硬币都进行了一次 Q 操作后，他发现了一个奇迹——所有硬币均为正面朝上。
小明想知道最开始有多少枚硬币是反面朝上的。于是，他向他的好朋友小M寻求帮助。
聪明的小M告诉小明，只需要对所有硬币再进行一次Q操作，即可恢复到最开始的状态。然而小明很懒，不愿意照做。于是小明希望你给出他更好的方法。帮他计算出答案。
输入格式
输入数据包含一行，两个正整数 n m，含义见题目描述。
输出格式
输出一个正整数，表示最开始有多少枚硬币是反面朝上的。
样例输入
2 3
样例输出
1
数据规模和约定
对于10%的数据，n、m
赞 光华已逝 幼苗
共回答了18个问题采纳率：88.9% 举报
#include
#include
#define M 10000
#define N 10000
using namespace std;
bool a[M][N];
void init(int m,int n)
{
int i,j;
for(i=1;i<=m;i++){
for(j=1;j<=n;j++){
a[i][j]=true;
}
}
}
void qTurn (int m,int n)
{
int x;
int y;
int i;
int j;
for (x =1; x<=m;x++ ){
for (y = 1; y<=n; y++ ){
for ( i=1; i<=m/ x;i++ ){
for (j=1; j<=n/y;j++ ){
a[i* x][j * y] =!a[i* x][j * y];
}
}
}
}
}
int sum(int m,int n){
int i,j;
int sum;
sum=0;
for(i=1;i<=m;i++){
for(j=1;j<=n;j++){
if(!a[i][j]) sum ++;
}
}
return sum;
}
int main(){
int m,n;
while(cin >> m){
cin >> n;
init(m,n);
qTurn(m,n);
cout << sum(m,n)<
}
这是模拟操作的做法，并不能保证所有的数据都正确，因为m，n很大的时候，数组太大。楼下的是正解。只有坐标为(i, j)，i和j都是完全平方数的硬币是才会被翻面，其他的硬币都会维持正面。
因为如果不是完全平方数的话有偶数个约数，会被翻转偶数次。而完全平方数有奇数个约数，比如4，有1,2,4三个约数，会被翻奇数次，反面的变为正面。初始反面的有sqrt(n) * sqrt(m)个。
再举个例子吧，比如a[2][4],此时2有2个约数1,2,4有3个约数1,2,4。它将被反转2*3=6次。只有奇数*奇数才是奇数，所以只有i和j都是完全平方数时，才会被翻面。#include
#include
using namespace std;
int main(){
unsigned long long m,n;
while(cin >> m){
cin >> n;
cout << (int)sqrt(m)*(int)sqrt(n)<
return 0;
}
#include
#define M 10000
#define N 10000
using namespace std;
bool a[M][N];
void init(int m,int n)
{
int i,j;
for(i=1;i<=m;i++){
for(j=1;j<=n;j++){
a[i][j]=true;
}
}
}
void qTurn (int m,int n)
{
int x;
int y;
int i;
int j;
for (x =1; x<=m;x++ ){
for (y = 1; y<=n; y++ ){
for ( i=1; i<=m/ x;i++ ){
for (j=1; j<=n/y;j++ ){
a[i* x][j * y] =!a[i* x][j * y];
}
}
}
}
}
int sum(int m,int n){
int i,j;
int sum;
sum=0;
for(i=1;i<=m;i++){
for(j=1;j<=n;j++){
if(!a[i][j]) sum ++;
}
}
return sum;
}
int main(){
int m,n;
while(cin >> m){
cin >> n;
init(m,n);
qTurn(m,n);
cout << sum(m,n)<
}
这是模拟操作的做法，并不能保证所有的数据都正确，因为m，n很大的时候，数组太大。楼下的是正解。只有坐标为(i, j)，i和j都是完全平方数的硬币是才会被翻面，其他的硬币都会维持正面。因为如果不是完全平方数的话有偶数个约数，会被翻转偶数次。而完全平方数有奇数个约数，比如4，有1,2,4三个约数，会被翻奇数次，反面的变为正面。初始反面的有sqrt(n) * sqrt(m)个。
再举个例子吧，比如a[2][4],此时2有2个约数1,2,4有3个约数1,2,4。它将被反转2*3=6次。只有奇数*奇数才是奇数，所以只有i和j都是完全平方数时，才会被翻面。#include
#include
using namespace std;
int main(){
unsigned long long m,n;
while(cin >> m){
cin >> n;
cout << (int)sqrt(m)*(int)sqrt(n)<
return 0;
}
1年前
8
可能相似的问题
-
1年前1个回答
-
1年前1个回答