萌新AA与棋盘

NC15055. 萌新AA与棋盘

描述

萌新AA喜欢对称，最近她喜欢把棋子放进她的棋盘中，这个棋盘是由 N×M 个格子构成的(1 <= N <= 1,000,000,000;1<=M<=1,000,000,000) 为了保证对称，AA 会以这样的方式摆放她的棋子。她把棋子放在棋盘正中央的方格内，如果不存在这样的方格，她就会停止。然后她以这个方格为中心把棋盘分成四部分，然后对于每个小棋盘进行上述的操作。下面是一个 N=7,M=15 的例子，其中'C'表示棋子

这样子，需要 21个棋子。如果 N=M=5 的话，AA只需要摆放一个棋子，因为分成的四个小棋盘分别是 2×2 的大小，无法在放进去新的棋子。现在，请你帮助 AA来计算，需要多少个棋子。

输入描述

一行两个整数 N,M

输出描述

一行一个整数，即需要的棋子数

示例1

输入:

7  15

输出:

示例2

输入:

3 1

输出:

说明:

不一定变成4个部分，存在中心位置即可

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 2ms, 内存消耗: 376K, 提交时间: 2020-10-06 10:20:53

#include<cstdio>
long f(long n,long m) 
{
	if(n%2==0||m%2==0)return 0;
	return f(n/2,m/2)*4+1;
}main() {
	long n,m;
	scanf("%ld%ld",&n,&m);
	printf("%ld",f(n,m));
}

C++11(clang++ 3.9) 解法, 执行用时: 5ms, 内存消耗: 508K, 提交时间: 2020-02-20 19:14:03

#include<iostream>
#include<algorithm>
using namespace std;
int n,m,p;
int main()
{
	cin>>m>>n;
	++m,++n;
	p=min(m&-m,n&-n);
	cout<<(p*p-1)/3<<'\n';
}

Python3(3.5.2) 解法, 执行用时: 31ms, 内存消耗: 3544K, 提交时间: 2020-02-08 19:41:33

n, m = map(int, input().split())
ans = 0
k = 1
while n & 1 and m & 1:
    ans += k
    k <<= 2
    n >>= 1
    m >>= 1
print(ans)