AcWing——倍增与或运算

拼搏现实的明天。 2023-10-10 20:13 46阅读 0赞

**目录**

一、或运算

1、题目

2、题目解读

3、代码

二、倍增

1、题目

2、题目解读

3、代码

--------------------

## 一、或运算 ##

[4975. 或运算 - AcWing题库][4975. _ - AcWing]

### 1、题目 ###

给定两个长度为 n 的整数序列 a1,a2,…,an以及 b1,b2,…,bn。

设 A=a1 or a2 or … or an，B=b1 or b2 or … or bn。

请你计算并输出 A+B 的值。

or 表示按位或运算。

输入格式

第一行包含整数 n。

第二行包含 n 个整数 a1,a2,…,an。

第三行包含 n 个整数 b1,b2,…,bn。

输出格式

一个整数，表示 A+B 的值。

数据范围

前 33 个测试点满足 1≤n≤10。  
所有测试点满足 1≤n≤1000，0≤ai,bi≤10⁹。

输入样例1：

5
    1 2 4 3 2
    2 3 3 12 1

输出样例1：

输入样例2：

10
    13 2 7 11 8 4 9 8 5 1
    5 7 18 9 2 3 0 11 8 6

输出样例2：

### 2、题目解读 ###

> 题目要求我们A、B两序列分别进行或运算，然后再进行相加处理。
> 
> 2种或运算：
> 
>     int a = 5;   // 二进制表示为 0101
>     int b = 3;   // 二进制表示为 0011
>     
>     a |= b;      // 使用位操作符"|="执行按位或运算并赋值给a
>     
>     System.out.println(a);   // 输出结果为 7（二进制表示为 0111）
> 
>     int a = 5;   // 二进制表示为 0101
>     int b = 3;   // 二进制表示为 0011
>     
>     int result = Integer.bitwiseOr(a, b);   // 使用位操作方法执行按位或运算
>     
>     System.out.println(result);   // 输出结果为 7（二进制表示为 0111）

### 3、代码 ###

import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
           Scanner sc=new Scanner(System.in);
            int n=sc.nextInt();
            long sumA=0;
            long sumB=0;
            for (int i=0;i<n;i++){
                int a=sc.nextInt();
                sumA|=a;
            }
            for (int i=0;i<n;i++){
                int b=sc.nextInt();
                sumB|=b;
            }
            System.out.println(sumA+sumB);
        }
    }

## 二、倍增 ##

[4976. 倍增 - AcWing题库][4976. _ - AcWing]

### 1、题目 ###

给定一个长度为 n 的整数序列 a1,a2,…,an。

你可以对该序列进行任意次倍增操作（也可以不进行任何操作）。

每次倍增操作可以任选序列中的一个元素，并将其乘以 2 或乘以 3。

我们的目标是让序列中所有元素的值都相等。

请你判断，目标是否能够实现。

输入格式

第一行包含整数 n。

第二行包含 n 个整数 a1,a2,…,an。

输出格式

如果可以让序列中所有元素的值都相等，则输出 `Yes`，否则，输出 `No`。

数据范围

前 66 个测试点满足 2≤n≤10。  
所有测试点满足 2≤n≤10⁵，1≤ai≤10⁹。

输入样例1：

4
    75 150 75 50

输出样例1：

Yes

输入样例2：

3
    100 150 250

输出样例2：

### 2、题目解读 ###

> 我们可以进行任意次倍增操作，将其乘以 2 或乘以 3，需要将序列都变成同一个数，如果可以，则说明这个序列所有数对除去 2,3 的所有质因子后剩余质因子的乘积都相同。

### 3、代码 ###

import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
            Scanner sc=new Scanner(System.in);
            int n=sc.nextInt();
            int[] arr=new int[n];
            for (int i=0;i<n;i++){
                arr[i]=sc.nextInt();
                while (arr[i]%2==0)
                    arr[i]/=2;
                while (arr[i]%3==0)
                    arr[i]/=3;
                if (i!=0&&arr[i]!=arr[i-1]){//判断也同时进行着
                    System.out.println("No");
                    return;
                }
            }
            System.out.println("Yes");
        }
    }

[4975. _ - AcWing]: https://www.acwing.com/problem/content/4978/
[4976. _ - AcWing]: https://www.acwing.com/problem/content/4979/