【牛客】WY49数对,JZ65不用加减乘除做加法

✨博客主页: XIN-XIANG荣
✨系列专栏:【牛客网刷题】
✨一句短话: 难在坚持,贵在坚持,成在坚持!

文章目录

一. 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

代码实现：

importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String args[]){Scanner sc =newScanner(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;}elseif(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结束运算

代码实现：

intAdd(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;}

提交结果：