پاسخ سوال قناد ناشی کوئرا

پاسخ سوال قناد ناشی کوئرا

در این نوشته تمرین “قناد ناشی” که در وب‌سایت کوئرا موجود است را برای شما کاربران عزیز حل کرده‌ایم.

پاسخ سوال قناد ناشی کوئرا

پروفسور باقر که یک کاربر ناشی است، به دلیل کمبود بودجه‌اش، در قنادی به کار مشغول شده است. او مسئول بریدن و تقسیم کردن کیک‌ها و شیرینی‌ها است. روزی ز سر سنگ مشتری‌ای داخل قنادی می‌شود و کیکی سفارش می‌دهد و از پروفسور درخواست می‌کند که آن کیک را برای k نفر برش دهد. یعنی جوری کیک را تکه تکه کند که در آخر مشتری بتواند به هر نفر از k نفر تعدادی تکه کیک بدهد جوری که در آخر به هر نفر به اندازه‌ی برابر کیک رسیده شود. یعنی به هر نفر باید دقیقا  k1​ از کیک برسد. تنها نکته‌ای که این وسط وجود دارد این است که طبق قوانین قنادی، در هر بار برش پروفسور فقط می‌تواند یک تکه از کیک را دقیقا به $d$ تکه‌ی برابر تقسیم کند. حالا مشکلی که برای پروفسور پیش آمده این است که پروفسور (برای صرفه جویی در کارش) دنبال کوچکترین d می‌گردد که با آن بتوان کیک را به طور مساوی بین k نفر تقسیم کرد. شما این کوچکترین $d$ را به او بگویید. برای مثال فرض کنید که k=4 و $d=8$: پروفسور باقر می‌تواند کیک را به 8 تکه تقسیم کند و مشتری می‌تواند به هر کدام از 4 نفر دو تکه بدهد، یا پروفسور اول کیک را به 8 تکه تقسیم کند و سپس دوباره هر تکه ایجاد شده را به $8$ تکه تقسیم کند و مشتری به هر نفر $16$ تکه بدهد تا به هر نفر به اندازه‌ی برابر کیک رسید. دوباره برای مثال اگر k=2، $d$ نمیتواند برابر 3 است. و باز برای مثال اگر $d$ برابر k باشد، می‌توان کیک را به طور مساوی بین $k$ نفر تقسیم کرد.

ورودی سوال قناد ناشی

در سطر اول ورودی عدد k آمده است که نمایانگر تعداد افرادی است که کیک باید بین آن‌ها به طور مساوی تقسیم شود.

$$2\le k\le 1000000$$

خروجی سوال قناد ناشی

تنها سطر خروجی باید شامل کوچکترین عدد $d$ باشد که می‌توان با آن کیک را بین $k$ نفر به طور مساوی تقسیم کرد.

حل سوال قناد ناشی

#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <string>
#include <string.h>
#include <math.h>
#include <queue>
#include <map>
using namespace std;
#define ll long long

bool isPrime(int num)
{
    if(num == 1)
        return false;
    for(int i=2; i<=sqrt(num); i++)
    {
        if(num % i == 0)
            return false;
    }
    
    return true;
}

int main()
{
    int k;
    cin >> k;
    
    ll hasel = 1;
    for(int i=1; i<sqrt(k); i++)
    {
        if(k % i == 0)
        {
            if(isPrime(i))
                hasel *= i;
            if(isPrime(k/i))
                hasel *= k/i;
        }
    }
    
    if(floor(sqrt(k)) == sqrt(k))
    {
        int jazr = sqrt(k);
        if(isPrime(jazr))
            hasel *= jazr;
    }
    
    
    cout << hasel;
    return 0;   
}

منبع سوال‌: وبسایت کوئرا

اگر روش حل بهتری برای “تمرین قناد ناشی” دارید برای ما ارسال کنید تا با نام خودتان به اشتراک بگذاریم. اگر سوال خاصی را مدنظر دارید در بخش نظرات برای ما ارسال کنید تا حل آن سوال را در الویت محتوای سایت بگذاریم.