home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

Count of pairs from 1 to a and 1 to b whose sum is divisible by N in C++

กำหนด a, b, n นับคู่ (x,y) ที่ 1 ≤ x ≤ a, 1 ≤ y ≤ b และ (x+y) % n == 0

ตัวอย่าง: a=2, b=3, n=2 → Output: 3

คู่: (1,1)=2, (1,3)=4, (2,2)=4 หาร 2 ลงตัว

วิธีแก้ปัญหา (O(n) แทน O(ab))

  1. นับจำนวน x ใน [1,a] ที่ mod n = r สำหรับทุก r (0..n-1)
  2. นับจำนวน y ใน [1,b] ที่ mod n = r
  3. คู่ที่ (x+y)%n==0 คือ x%r + y%(n-r)%n == 0
  4. รวม count_x[r] * count_y[(n-r)%n]

ตัวอย่างโค้ด C++ (Optimized)

#include <bits/stdc++.h>
using namespace std;

long long countPairs(int a, int b, int n) {
    vector cntA(n), cntB(n);
    for(int r=0;r

Input

a=2, b=20, n=4

Output

10