# PBinfo #1950 – PXP – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Cerința
Se dă un şir format din N numere naturale nenule. Spunem că un număr e fericit dacă se poate scrie ca suma pătratelor a două numere naturale. Notăm cu K numărul numerelor fericite din şir şi cu P produsul acestora. Aflaţi numărul K precum şi două numere naturale care au suma pătratelor egală cu PE, unde E este un număr natural dat.

Date de intrare
Fișierul de intrare pxp.in conține pe prima linie numerele N şi E , iar pe a doua linie N numere naturale separate prin spațiu.

Date de ieșire
Fișierul de ieșire pxp.out va conține pe prima linie numărul K, reprezentând numărul numerelor fericite din şir iar pe  a doua linie cele două numere care au suma pătratelor egală cu PE.

Restricții și precizări

1 ≤ N ≤ 100.000
1 ≤ E ≤ 3
numerele din şir sunt mai mici decât 1.000.001 şi cel puţin un număr din şir este fericit
1 ≤ P ≤ 1036
pentru a doua cerinţă se va afişa orice soluţie, fiecare test având soluţie
pentru prima cerinţă se acordă 40p, iar pentru a doua 60p
30% din teste au P ≤ 1000000, iar alte 40% au P ≤ 1018
80% din teste au E=1, 10% au E=2 şi 10% au E=3

Exemplu:
pxp.in

5 1
11 2 13 7 5
pxp.out

3
3 11
Explicație
Avem N=5 şi E=1. În şir sunt 3 numere fericite, 2, 13 şi 5, deoarece 2=12+12 ,  13=22+32 şi 5=12+22. Produsul lor este 130=32+112, deci două numere pentru care suma pătratelor este P1 sunt 3 şi 11.

## Cod sursă C++

```cpp
#include <fstream>
using namespace std;
ifstream f("pxp.in");
ofstream g("pxp.out");
unsigned long long n,i,j,x,y,t,u,c[101],d[1000],q[1000],m,nr,z,e,k;
int a[1000001],b[1000001] ;
char v[1000001] ;
int main()
{
    f >> n >> e ;
    for ( i=0 ; i<=1000 ; i++ )
      for ( j=i ; j<=1000 ; j++ )
      {
          x = i*i + j*j ;
          if ( x<=1000000)
          {
              v[x] = 1 ;
              a[x] = i ;
              b[x] = j ;
          }
      }
    m = 0 ;
    nr = 0 ;
    for ( i=1 ; i<=n ; i++ )
    {
        f >> x ;
        if ( v[x]==1 )
        {
            nr++ ;
            if ( x!=1 )
            {
               m++ ;
               c[m] = x ;
            }
        }
    }
    if ( nr > m ) { m++ ; c[m] = 1 ;} ;
    x = a[c[1]] ;
    y = b[c[1]] ;
    for ( i=2 ; i<=m ; i++ )
    {
        t = x*a[c[i]]+y*b[c[i]] ;
        if ( x*b[c[i]]>y*a[c[i]]) u = x*b[c[i]]-y*a[c[i]] ;
        else u = y*a[c[i]]-x*b[c[i]] ;
        x = t ;
        y = u ;
    }
    g << nr << "\n" ;
    if ( e==1 )
    {
        g << x << " " << y ;
    }
    if ( e==2 )
    {
        if ( x<y ){ t=x ; x=y ; y=t; }
        t = x-y ;
        u = x+y ;
        m = 0 ;
        while(t!=0)
        {
            m++ ;
            c[m] = t%10 ;
            t = t / 10 ;
        }
        t = 0 ;
        for ( i=1 ; i<=m ; i++ )
        {
           z = c[i] * u + t ;
           c[i] = z % 10 ;
           t = z / 10 ;
        }
        if ( t>0 ) g << t ;
        for ( i=m ; i>=1 ; i-- ) g << c[i] ;
        g << " " ;
        t = 2 * x ;
        u = y ;
        m = 0 ;
        while(t!=0)
        {
            m++ ;
            c[m] = t % 10 ;
            t = t / 10 ;
        }
        t = 0 ;
        for ( i=1 ; i<=m ; i++ )
        {
           z = c[i] * u + t ;
           c[i] = z % 10 ;
           t = z / 10 ;
        }
        if ( t>0 ) g << t ;
        for ( i=m ; i>=1 ; i-- ) g << c[i] ;
    }
    if ( e==3 )
    {
        d[1] = 1 ;
        i = 1 ;
        for( j=1 ; j<=m ; j++ )
        {
            t = 0 ;
            for( k=1 ; k<=i ; k++ )
            {
                z = c[j] * d[k] + t ;
                d[k] = z % 10 ;
                t = z / 10 ;
            }
            while (t>0){i++ ; d[i]=t%10 ; t=t/10;}
        }
        t = 0 ;
        for ( j=1 ; j<=i ; j++ )
        {
            z = d[j] * x + t ;
            q[j] = z % 10 ;
            t = z / 10 ;
        }
        if ( t>0 ) g << t ;
        for( j=i ; j>=1 ; j-- ) g << q[j] ;
        g << " " ;
        t = 0 ;
        for ( j=1 ; j<=i ; j++ )
        {
            z = d[j] * y + t ;
            q[j] = z % 10 ;
            t = z / 10 ;
        }
        if ( t>0 ) g << t ;
        for( j=i ; j>=1 ; j-- ) g << q[j] ;
    }
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1950)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1950/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1950/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)