Zadatak PREBROJ

Pitanja i problemi
1

Da li je neko uspeo ovaj zadatak da uradi bez TLE i kako?

2

Uf, to onaj zadatak gde treba da se odredi broj najbliži 100? Imao sam bod (:

3

Zadatak je isti bio prošle godine na drzavnom…
Čak ni tamo ne vidim “direktno” rešenje… zanima me uopšte da li neko ima rešenje da podeli.

https://dms.rs/wp-content/uploads/2020/08/DrzavnoTakmicenje2020Bilten.pdf (6 strana)

5

Obrisao autor?

6

nije htelo da mi uvuce redove a tako kod izgleda jako cudno

1 Like
7

Da. Ali u suštini se vidi.

8 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define MAXN 10000
#define fi first
#define se second
#define mod 1000000007LL
#define endl "\n"

ll n, m, k, q, l, r, x, z;
string s,t;
ll res=0,tmp=0;
ll a[MAXN],b[MAXN],c[MAXN],dp[MAXN],cnt[MAXN]={0};
bool prekini=false;
bool visited[MAXN]={false};
vector<int> adj[MAXN];
pair<ll,ll> p[MAXN];


void ReadArray(ll* arr,int d){
    for(int i=0;i<d;i++){
        cin>>arr[i];
    }
}

void OutArray(ll* arr,int d){
    for(int i=0;i<d;i++){
        cout<<arr[i]<<" ";
    }
    cout<<endl;
}

bool kvadrat(ll n){
    if(n==0){
        return false;
    }
    ll koren=sqrt(n);
    return (koren*koren==n);
}

void solve(){
    cin>>n;
    for(int i=0;i<n;i++){
        double broj;
        cin>>broj;
        for(int y=1;y<=sqrt(broj);y++){
            if(kvadrat(broj-y*y)){
                res++;
                break;
            }
        }
    }
    cout<<res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int t;
    //cin>>t;
    t=1;
    while(t--){
        solve();
    }
    return 0;
}
1 Like
9

Evo ga sad je sve uvuceno pa je valjda lakse da se vidi.

1 Like
10

Lepo! Hvala i meni je lepo da vidim kako su drugi to uradili, još samo da ga prekucam u python :smile:

2 Likes
11

Takodje, mislim da postoji teorema da ako postoji prost broj p medju prostim faktorima nekog broja m i p=3(mod4) to znaci da broj ne moze da se prikaze kao zbir dva potpuna kvadrata. U ovo nisam siguran ali bi trebalo da vazi.

12

Ako imas neki problem javi.

1 Like
13

Да, то је једна од Фермаових теорема у теорији бројева.

2 Likes