指定尺寸正方形瓷砖适配矩形地板的数量计算问题

Alright, let's work through how to solve this problem where we need to count how many tile sizes can perfectly cover each given floor.

First, Let's Clarify the Rule #

The key condition here is: a d×d tile can cover an a×b floor if and only if gcd(a, b) mod d == 0. Let's break why this makes sense:

• Let g = gcd(a, b) — this means we can split the floor into g×g logical blocks (since a = g*x and b = g*y where x and y are coprime, meaning they share no common factors other than 1).
• If d divides g (i.e., g mod d == 0), then each g×g block can be split into (g/d)×(g/d) d×d tiles. Scaling this to the entire floor, we’ll get a perfect fit with no gaps or overlaps.

Step-by-Step Approach #

Here's a straightforward, easy-to-implement way to tackle this:

1. Deduplicate Tile Sizes: Since we’re counting types of tiles, duplicate sizes should only be counted once (e.g., two 2×2 tiles still count as one type).
2. Calculate GCD for Each Floor: For every a×b floor, compute the greatest common divisor of a and b.
3. Count Valid Tiles: For each floor, count how many unique tile sizes divide its GCD (i.e., satisfy gcd(a,b) mod d == 0).

Example Code Implementation (Python) #

import math

def count_valid_tiles(tile_sizes, floor_specs):
    # Remove duplicate tile sizes to avoid overcounting
    unique_tiles = set(tile_sizes)
    valid_counts = []
    
    for a, b in floor_specs:
        floor_gcd = math.gcd(a, b)
        count = 0
        for d in unique_tiles:
            if floor_gcd % d == 0:
                count += 1
        valid_counts.append(count)
    
    return valid_counts

# Test the function with sample inputs
sample_tiles = [2, 3, 4, 6]
sample_floors = [(12, 18), (8, 10), (6, 6)]
print(count_valid_tiles(sample_tiles, sample_floors))  # Output: [3, 1, 4]

Explanation of the Example #

• For the floor (12,18), gcd(12,18)=6. Valid tiles are 2, 3, 6 → 3 types total.
• For the floor (8,10), gcd(8,10)=2. Only the 2×2 tile fits → 1 type.
• For the floor (6,6), gcd(6,6)=6. All 4 tile sizes divide 6 → 4 types.

Optimization Note #

If you’re working with a huge number of tiles or floors, you can pre-process the tile sizes into a sorted list, or precompute a divisor frequency map to speed up counting. But for most practical cases, the simple loop approach works perfectly well.

内容的提问来源于stack exchange，提问作者piternet