ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1846. НОД 2010

WA on test#4
Послано Aditya Singh 23 окт 2017 12:07
Please give test-case -4 for this problem
MY code

#include <bits/stdc++.h>
using namespace std;
#define repl(i,x,n) for(long long i=(long long)(x);i<(long long)(n);i++)
#define rep(i,x,n) for(long i=long(x);i<long(n);i++)
long HCF(long a,long b)
{
    if(a==0) return b;
    return HCF(b%a,a);
}
int main()
{
    ifstream cin("input.in");
    ofstream cout("output.out");
    ios::sync_with_stdio(0);cin.tie(0);
    long n,x,h=-1,l=0;
    unordered_map<long,long> m;
    set<long> s;
    char c;
    cin>>n;
    rep(j,1,n+1)
    {
        cin>>c>>x;
        if(c=='+')
        {
            l++;
            s.insert(x);
            if(h==-1)
            {
                h=x;
                cout<<x<<"\n";
            }
            else
            {
                h=HCF(h,x);
                cout<<h<<"\n";
            }
            long p=sqrt(x);
            rep(i,1,p+1)
            {
                if(x%i==0)
                {
                    m[i]++;
                    m[x/i]++;
                }
            }
            if(p*p==x)
                m[p]--;
            //for(auto i:m)
            //    cout<<i.first<<" "<<i.second<<"\n";
            //cout<<"\n";
        }
        else
        {
            s.erase(x);
            l--;
            long q;
            if(!s.empty())
                q=*s.begin();
            else
            {
                cout<<1<<"\n";
                continue;
            }
            //cout<<q<<"-----\n";
            long p=sqrt(x);
            rep(i,1,p+1)
            {
                if(x%i==0)
                {
                    m[i]--;
                    m[x/i]--;
                }
            }
            if(p*p==x)
                m[p]++;
            long w=0;
            rep(i,1,sqrt(q)+1)
                if(q%i==0)
                {
                    if(m[i]==l)
                        w=max(w,i);
                    if(m[q/i]==l)
                        w=max(w,q/i);
                    //cout<<w<<"--n---n--n\n";
                }
            cout<<w<<"\n";
            //for(auto i:m)
            //    cout<<i.first<<" "<<i.second<<"\n";
            //cout<<"\n";
        }
    }
    return 0;
}
Re: WA on test#4
Послано tishinilia 26 янв 2019 19:12
try:
5
+ 2
- 2
+ 2
- 2
+ 2