Ionel are de rezolvat mai multe probleme de divizibilitate. Unele dintre ele îi cer să afle câte numere au anumite proprietăţi. Vă rugăm să-l ajutaţi să termine tema mai repede.

Cerința

Scrieţi un program care citeşte un număr natural n şi două numere prime u şi v mai mici decât 10 şi determină câte numere naturale mai mici sau egale cu n au proprietatea că nu sunt divizibile nici cu u, nici cu v.

Date de intrare

Fișierul de intrare numere20.in conţine pe prima linie numărul natural n şi cifrele u şi v, separate prin câte un spaţiu.

Date de ieșire

Fișierul de ieșire numere20.out va conţine o singură linie pe care va fi scris numărul de numere naturale mai mici sau egale cu n care nu sunt divizibile nici cu u, nici cu v.

Restricții și precizări

• Numărul natural n are cel mult 100 de cifre

Exemplu

numere20.in

30  3  7

numere20.out

17

Explicație

Numerele care au proprietatea din enunţ sunt: 1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20, 22, 23, 25, 26, 29.

#include <bits/stdc++.h>


using namespace std;

ifstream cin("numere20.in");
ofstream cout("numere20.out");

int a[101] , b[101] , c[101] , n[101];
void impartire(int a[] , int &n , int x)
{
      int c = 0;
      for(int i = 1 ; i <= n ; i++)
      {
          c = c * 10 + a[i];
          a[i] = c / x;
          c =  c % x;
      }
      if(a[1] == 0)
      {
          for(int i = 1 ; i <= n ; i++)
              a[i] = a[i+1];
          a[n] = 0;
          n--;
      }
}

void invers(int a[] , int n)
{
    int i = 1 , j = n;
    while(i <= j)
    {
        swap(a[i] , a[n - i + 1]);
        i++;
        j--;
    }
}

void scadere(int a[] , int &n , int b[] , int m)
{
    invers(a , n);
    invers(b , m);
    int t = 0;
    for(int i = 1 ; i <= n ; i++)
    {
        int c = a[i] - b[i] + t;
        if(c < 0)
        {
            c += 10;
            t = -1;
        }
        else t = 0;
        a[i] = c;
    }
    if(a[n] == 0) n--;
    invers(a , n);
}

void adunare(int a[] , int &n , int b[] , int m)
{
    invers(a , n);
    invers(b , m);
    int t = 0;
    if(m > n) n = m;
    for(int i = 1 ; i <= n ; i++)
    {
        int c = a[i] + b[i] + t;
        a[i] = c % 10;
        t = c / 10;
    }
    if(t > 0) a[++n] = t;

    invers(a , n);
}
int main()
{
    ///nr = n / u + n / v - n /(u*v);
    int u , v , cnt = 0;
    char s[101];
    cin >> s >> u >> v;
    int nr = strlen(s);
    for(int i = 0 ; i < nr ; i++) a[i+1] = s[i] - '0' , b[i+1] = s[i] - '0' , c[i+1] = s[i] - '0' , n[i+1] = s[i] - '0';
    int nr1 = nr , nr2 = nr , num = nr;
    impartire(a , nr , u);
    impartire(b , nr1 , v);
    impartire(c , nr2 , u*v);
    scadere(n , num , a , nr);
    scadere(n , num , b , nr1);
    adunare(n , num , c , nr2);
    for(int i = 1 ; i <= num ; i++) cout << n[i];
}