题目

给你一个正整数n,判断n能否被3、5、8、11中的一个或多个数整除。

输入

第一行是一个正整数T代表测试案例的数量。(1<=T<=100)

从第二行到第T+1行,每行是一个(可能超过int范围的)正整数n。(1<=n<=1e50)

输出

针对每组案例,按从小到大的顺序输出可以整除n的数字。

数字之间用空格隔开,每行最后一个数字后面没有空格。

如果n不能被这四个数中的任何一个数整除则输出No。

每组案例结束以后都要换行。

样例输入

  • 3
  • 123456789
  • 2341232402462055420
  • 9741427

样例输出

  • 3
  • 3 5
  • No

HINT

  • 注意数据范围。

思路

像数据这么大的时候肯定不能像平时那样子鲁莽
请看下面我的整理

整除规则:

  • 任何数都能被1整除
  • 个位数上是2 4 6 8 0 都能被2整除
  • 所有位数之和能被3整除 则能被3整除
  • 最后两位能被4整除 则能被4整除
  • 个位数是0或5 则能被5整除
  • 一个数同时能被2和3整除 则能被6整除
  • 最后三位能被8整除 则能被8整除
  • 一个数能同时被3和4整除 则能被12整除
  • 11整除特征:
    能被11整除的数的规律:一个整数由右边个位向左边数,奇位上的数字之和与偶位上的数字之和的差如果能被11整除(包括0),则这个数就能被11整除,这种方法叫“奇偶位差法”。

AC代码

#include <iostream>
#include <string>
#include <cmath>
#include <list>
using namespace std;
bool i3(string n)
{
    int s = 0;
    for (int i = 0; i < n.length(); i++)
    {
        s += (n[i] - '0');
    }
    if (s % 3 == 0)
        return true;
    return false;
}
bool i5(string n)
{
    if (n.back() == '0' || n.back() == '5')
        return true;
    return false;
}
bool i8(string n)
{
    int s = 0, k = 100;
    if (n.length() == 1)
    {
        s = n.back() - '0';
    }else if(n.length() == 2)
    {
        s = (n[0] - '0')*10 + (n[1] - '0');
    }
    else
    {
        for (int i = n.length() - 3; i < n.length(); i++)
        {
            s += ((n[i] - '0') * k);
            k /= 10;
        }
    }
    // cout << s << endl;
    if (s % 8 == 0)
        return true;
    return false;
}
bool i11(string n)
{
    int o = 0, p = 0;
    for (int i = 0; i < n.length(); i++)
    {
        int k = n[i] - '0';
        if (i % 2)
        {
            o += k;
        }
        else
            p += k;
    }
    if (abs(o - p) % 11 == 0)
        return true;
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    int t;
    string n;
    cin >> t;
    while (t--)
    {
        list<int> res;
        cin >> n;
        if (i3(n))
            res.push_back(3);
        if (i5(n))
            res.push_back(5);
        if (i8(n))
            res.push_back(8);
        if (i11(n))
            res.push_back(11);
        if (res.size() == 0)
            cout << "No" << endl;
        else
        {
            int b = 0;
            while (res.size())
            {
                if (b)
                    cout << " ";
                else
                    b = 1;
                cout << res.front();
                res.pop_front();
            }
            cout << endl;
        }
    }
    return 0;
}
Last modification:April 3rd, 2020 at 02:46 pm
如果觉得我的文章对你有用,请随意赞赏