题解：P16874 [GKS 2022 #B] Palindromic Factors

zhanghanze123 · 2026-06-11 18:14:21 · 题解

题目大意

给定 t 个正整数 n，求出每个正整数 n 有几个因数是回文数。

解题思路

由于 n \le 10^{10}，直接枚举肯定不行。

显然我们可以枚举到 \sqrt{n}，每次取 i \in [1,\sqrt{n}]，若 i 为 n 因数，判断它是否回文；若 \dfrac{n}{i}\ne i，判断 \dfrac{n}{i} 是否回文。

AC Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int input();//快读
void print(int x);//快写
signed main(void){
    int t=input();//读入
    for (int T = 1;T<=t;T++){
        cout<<"Case #"<<T<<": ";//按格式输出
        int n=input(),ans=0;//读入
        for (int i = 1;i*i<=n;i++){
            if (n%i) continue;//如果 i 不是 n 的因数就跳过
            string str=to_string(i),s=to_string(i);//转为字符串判回文
            reverse(str.begin(),str.end());
            if (str==s) ++ans;//如果 i 回文
            if (n/i!=i){//判断 n/i 是否等于 i，如果不相等，就判断 n/i 是否回文
                str=to_string(n/i),s=to_string(n/i);
                reverse(str.begin(),str.end());
                if (str==s) ++ans;
            }
        }
        print(ans),puts("");
    }
    return 0;
}
inline int input(){
    int x=0,f=1;
    char c=getchar();
    while (!isdigit(c)){
        if (c=='-') f=-1;
        c=getchar();
    }
    while (isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
void print(int x){
    if (x<0){
        putchar('-');
        x=-x;
    }
    if (x<10) putchar(x+'0');
    else{
        print(x/10);
        putchar(x%10+'0');
    }
}

AC 记录。