题目重述

给定正整数 $a,b,l$，要求找到所有满足

的不同 $k$ 值的个数，其中 $x,y,k$ 都是非负整数。

核心思想

由等式 $l = k \cdot a^x \cdot b^y$ 可得：

因此，$k$ 必须是整数，即 $a^x \cdot b^y$ 必须能整除 $l$。

关键观察

1. $x$ 和 $y$ 的范围有限

   • 因为 $a \ge 2$，当 $x$ 增大时，$a^x$ 增长很快。
   • $2^{20} = 1,048,576$ 已经超过 $l$ 的最大值 $10^6$。
   • 所以 $x$ 最多到 $20$ 左右，$y$ 同理。
   • 标程中用了 $34$ 作为上限（$2^{34} > 10^6$ 很多，足够安全）。

2. 枚举所有可能的 $(x,y)$ 组合

   • 先固定 $x$，从 $l$ 中除去 $a^x$ 得到中间值 $x\_val$。
   • 然后从这个中间值中不断除去 $b$ 的幂次，得到不同的 $k$。
   • 用 set 自动去重。

标程详解

void solve(int tc){
    int a, b, l;
    cin >> a >> b >> l;
    set<int> ans;
    
    for(int i = 0; i <= 34; ++i){        // i 表示 x 的值
        int x = l;
        bool fail = false;
        
        // 从 l 中除去 a^i
        for(int _ = 0; _ < i; ++_){
            if(x % a){                    // 如果不能整除，说明这个 i 不可行
                fail = true;
                break;
            }
            x /= a;
        }
        if(fail) break;                   // 如果 a^i 不能整除 l，更大的 i 也不行
        
        // 现在 x = l / a^i
        // 不断从 x 中除去 b 的幂次，得到不同的 k
        while(true){
            ans.insert(x);                // 当前 x 就是一个可行的 k
            if(x % b) break;              // 如果不能继续除 b，就停止
            x /= b;
        }
    }
    cout << ans.size();
}

算法流程示例

以第一个样例 $a=2,b=5,l=20$ 为例：

• $i=0$（$x=0$）：$x=20$，然后不断除 $5$：

  • $20 \to ans\{20\}$，$20\%5=0$，除以 $5$ 得 $4$
  • $4 \to ans\{20,4\}$，$4\%5\neq0$，停止

• $i=1$（$x=1$）：$x=20/2=10$，然后除 $5$：

  • $10 \to ans\{20,4,10\}$，$10\%5=0$，除以 $5$ 得 $2$
  • $2 \to ans\{20,4,10,2\}$，$2\%5\neq0$，停止

• $i=2$（$x=2$）：$x=20/4=5$，除 $5$：

  • $5 \to ans\{20,4,10,2,5\}$，$5\%5=0$，除以 $5$ 得 $1$
  • $1 \to ans\{20,4,10,2,5,1\}$，$1\%5\neq0$，停止

• $i=3$：$x=20/8$ 不是整数，失败，循环结束

最终 $ans = \{1,2,4,5,10,20\}$，共 $6$ 个。

复杂度分析

• 外层循环 $i$ 最多 $34$ 次
• 内层每次最多除 $b$ 约 $\log_b l$ 次
• 总复杂度 $O(34 \cdot \log_b l)$，非常快

总结

关键点：

1. 注意到 $x,y$ 的取值范围很小（$0$ 到约 $20$）
2. 枚举所有可能的 $a^x$，然后从 $l/a^x$ 中不断除去 $b$ 的幂次
3. 用集合自动去重

这种方法简单高效，完全满足题目 $t \le 10^4, l \le 10^6$ 的限制。