Informatics Olympiad YBT 1171: factors of large integers | 1.6 13: factors of large integers

【 Topic link 】

ybt 1171： The factor of a large integer
OpenJudge NOI 1.6 13: The factor of a large integer

【 Topic test site 】

1. High precision

Investigate ： High precision die low precision
Explanation of high-precision calculation

【 Their thinking 】

First treat the numbers involved in the operation as low precision numbers , To solve this problem , It's not hard to write code ：

int main()
{
    
    int k, c;
    cin >> c;
    bool hasK = false;
    for(int k = 2; k <= 9; ++k)
    {
    
        if(c % k == 0)
        {
    
            cout << k << ' ';
            hasK = true;
        }
    }
    if(hasK == false)
        cout << "none";
    return 0;
}

In this question ,c Is a high-precision number ,k The scope is 2~9, It is still a low precision number . Then just put c%k==0 Rewritten as high precision die low precision , To solve the problem .

【 Solution code 】

solution 1： function + Array

#include<bits/stdc++.h>
using namespace std;
#define N 35
// Convert a character array to a number array   The number array starts from 1 Position to len Location , Save the numbers from low to high , The first 0 Position saves the number of digits 
void toNum(char s[], int a[])
{
    
    a[0] = strlen(s);
    for(int i = 1; i <= a[0]; ++i)
        a[i] = s[a[0] - i] - '0';
}
// High precision die low precision 
int Mod(int a[], int b)
{
    
    int x = 0;
    for(int i = a[0]; i >= 1; --i)
        x = (x * 10 + a[i]) % b;
    return x;
}
int main()
{
    
    int n, k, c[N] = {
    }; 
    char s[N];
    bool hasK = false;
    cin >> s;
    toNum(s, c);
    for(k = 2; k <= 9; ++k)
    {
    
        if(Mod(c, k) == 0)
        {
    
            cout << k << ' ';
            hasK = true;
        }
    }
    if(hasK == false)
        cout << "none";
    return 0;
}

solution 2： Overloaded operator in class

#include <bits/stdc++.h>
using namespace std;
#define N 35
struct HPN
{
    
    int a[N];// Array of numbers 
    HPN()
    {
    
        memset(a, 0, sizeof(a));
    }
    HPN(char s[])
    {
    
        memset(a, 0, sizeof(a));
        int len = strlen(s);
        for(int i = 0; i < len; ++i)
            a[len - i] = s[i] - '0';
        a[0] = len;
    }
    int operator % (int b) // High precision die low precision 
    {
    
        int x = 0;
        for(int i = a[0]; i >= 1; --i)
            x = (x * 10 + a[i]) % b;
        return x;
    }
};
int main()
{
    
    char s[N];
    cin >> s;
    HPN c(s);// High precision digital c 
    bool hasK = false;
    for(int k = 2; k <= 9; ++k)
    {
    
        if(c % k == 0)// High precision die low precision  
        {
    
            cout << k << ' ';
            hasK = true;
        }
    }
    if(hasK == false)
        cout << "none";
    return 0;
}