【题解】StarryCoding P259 好奇怪好奇怪

题目传送门：P259 好奇怪好奇怪 | StarryCoding算法竞赛平台

题目描述

$Piper$喜欢一些奇怪的数字。对于一个奇怪的数字，它的十进制表示中只包含数字$4$和$7$。例如：$47、774、4$是奇怪的数字，$46、2024$就不是。

$Piper$认为能被奇怪的数字整除的数字是有些奇怪的数字，现给一个数字$n$，请判断这个数字是否有些奇怪。

输入描述

第一行包含整数$t$($1\le t\le 1000$) - 测试用例数。

接下来$t$行，每行包含一个整数$n(1\le n\le 1000)$ - 需要检查的数字。

保证$n$的总和不超过1000。

输出描述

打印$t$个答案–每个测试用例一个。

对于$i$-th 测试用例如果数字是有些奇怪的，在唯一一行打印“YES”(不带引号)，否则，打印“NO”。

输入样例1

3
47
16
78

输出样例1

YES
YES
NO

思路

因为数据量较小，所以可以将$n$的所有因数枚举出来并逐一检查是否为奇怪的数字即可得出答案。

感兴趣的友友们可以思考一下数据范围增大的话怎么解。

代码

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

bool check(int n)
{
    while(n)
    {
        if(n % 10 != 4 && n % 10 != 7)
        {
            return false;
        }
        n /= 10;
    }
    return true;
}

void solve()
{
    int n; cin >> n;
    for(int i = 1; i * i <= n; ++i)
    {
        if(n % i == 0)
        {
            if(check(i) || check(n / i))
            {
                cout << "YES" << '\n';
                return;
            }
        }
    }
    cout << "NO" << '\n';
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _; cin >> _;
    while(_--) solve();
    return 0;
}

本题由codeforces上的122A改编而成