【牛客】WY49数对,JZ65不用加减乘除做加法
✨博客主页: XIN-XIANG荣
✨系列专栏:【牛客网刷题】
✨一句短话: 难在坚持,贵在坚持,成在坚持!
文章目录
- 一. WY49数对
- 题目描述:
- 解题思路：
- 代码实现：
- 提交结果：
- 二. JZ65不用加减乘除做加法
- 题目描述:
- 解题思路：
- 代码实现：
- 提交结果：
一. WY49数对
题目描述:
牛牛以前在老师那里得到了一个正整数数对(x, y), 牛牛忘记他们具体是多少了。
但是牛牛记得老师告诉过他x和y均不大于n, 并且x除以y的余数大于等于k。
牛牛希望你能帮他计算一共有多少个可能的数对。
输入描述：
输入包括两个正整数n,k(1 <= n <= 10^5, 0 <= k <= n - 1)。
输出描述：
对于每个测试用例, 输出一个正整数表示可能的数对数量。
示例1
输入：5 2
输出：7
说明：
满足条件的数对有(2,3),(2,4),(2,5),(3,4),(3,5),(4,5),(5,3)
链接： 点这里
来源： 牛客网
解题思路：
先考虑除数y的取值，题目中要求余数余数>=k，所以除数要>k，所以y的取值范围显然属于区间[k+1, n]
要注意观察余数的规律，余数呈现周期性变化，当除数为y时，余数从1到y-1，末尾还有一个0，这就是一个周期；而除数从1到n一个周期为一个小区间，可以将从1到n划分为 t=n/y 个小区间；
[1, 2, …, y]
[y+1, y+2, …, 2y]
[2y+1, 2y+2, …, 3y]
…
[ty+1, ty+2, …, n]
每个周期内满足的被除数是y-k个，
最后一个区间如果是不完整周期，需要单独进行计算（因为 0 出现在周期序列的最后一个元素，不完整区间中周期末尾是没有0的）；最后一个不完整周期是1 到 n%y，所以 k!=0 时个数是n%y-k+1；当 k=0 时，个数为n%y
代码实现：
import java.util.Scanner;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
long count = 0;
for(int y = k+1; y <= n; y++) {
int ret = (n/y) * (y-k);
if(n%y>=k && k!=0) {
ret += n%y-k+1;
}else if(n%y>k && k==0) {
ret += n%y;
}
count += ret;
}
System.out.println(count);
}
}
提交结果：
二. JZ65不用加减乘除做加法
题目描述:
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
数据范围：两个数都满足 −10≤n≤1000
进阶：空间复杂度 O(1)O(1)，时间复杂度 O(1)O(1)
示例1
输入：1,2
返回值：3
示例2
输入：0,0
返回值：0
链接： 点这里
来源： 牛客网
解题思路：
这个题不能使用 +、-、*、/ 四则运算符号，那么跟计算相关的就应该考虑位运算了，要使用位运算完成相加，要理清一个计算思想：我们在计算时先不考虑进位实现不进位的运算，然后再实现进位的运算，最后把进位和不进位的结果相加就是最终的计算结果，这个过程可能需要多次循环执行，直到不需要进位为止。
先以十进制为例：
15+07 ， 先计算不考虑进位的相加结果 12 （因为 5+7 的不考虑进位的结果是 2 ，再加上15的十位），然后计算进位 5+7 进位是 10 ，则 10 与 12 再次相加，此时没有需要再进位的 ，结果为22，计算结束。
位运算是基于二进制的，计算的思想不变，不同点在于位运算符的运用：
与十进制相同，先计算不考虑进位的相加结果（ 0+0 得 0 ， 1+1 进位得 0 ， 1+0 得 1 ），使用异或（^）可以实现效果（异或是相同为0相异为1）；
然后计算相加的进位结果（同 1 的位置左移一位即可），两数按位与（&）后再左移一位即可达到进位效果。（这两个1相加会进位，高一位会加1，所以让所有能进位的位数保留1再整体左移达到效果）
再将进位与不进位的结果相加，也就是循环上述过程，直到不再进位，计算结束。
计算示例：
5 (0101) + 7 (0111)
不考虑进位的相加结果 0101^0111 -> 0010
相加的进位 0101&0111 -> 0101 因为进位左移得到 1010
1010 + 0010
不考虑进位的相加结果 1010 ^ 0010 -> 1000
相加的进位 1010 & 0010 -> 0010 因为进位左移得到 0100
1000 + 0100
不考虑进位的相加结果 1000 ^ 0100 -> 1100
相加的进位 1000 & 0100 -> 0000 进位为0结束运算
代码实现：
int Add(int num1, int num2 ) {
int sum = num1;
int add = num2;//需要累加的的值
while(add != 0)
{
//不考虑进位两数异或相加
int tmp = sum ^ add;
//两数相与得到需要进位的二进制位
//再左移一位二进制位达到进位效果
add = (sum & add) << 1;
//更新sum的值
sum = tmp;
//循环上述过程再将进位值加上，
//直到相加至不需要再进位即可
}
return sum;
}
提交结果：
