একটি ধনাত্মক পূর্ণসংখ্যা $N$
দেওয়া থাকবে, তোমাকে এর নিঃসঙ্গ ভাজক খুঁজে বের করতে হবে। এখন নিশ্চয়ই ভাবছো নিঃসঙ্গ ভাজক আবার কী, তাই না? একটি সংখ্যা $N$
-এর নিঃসঙ্গ ভাজক হলো তার একমাত্র ভাজক, যার ঠিক $K$
-সংখ্যক ভাজক আছে। যদি এরকম একাধিক ভাজক থাকে যার ঠিক $K$
-সংখ্যক ভাজক আছে, তাহলে সে ভাজকগুলো নিঃসঙ্গ নয়।
প্রথমে বলেছিলাম একটি ধনাত্নক পূর্ণসংখ্যা $N$
দেব, তোমাকে এর নিঃসঙ্গ ভাজক বের করতে হবে। কিন্তু আমি আমার মত পরিবর্তন করে ফেলেছি। একটি সংখ্যা দেওয়ার পরিবর্তে আমি তোমাকে একটি সংখ্যার সীমা $[L, R]$
এবং একটি ধনাত্নক পূর্ণসংখ্যা $K$
দেব। তোমাকে $[L, R]$
সীমার সংখ্যাগুলো থেকে (ইনক্লুসিভ অর্থাৎ, $L$
ও $R$
সহ) সেই সংখ্যাটি খুঁজে বের করতে হবে যার বৃহত্তম নিঃসঙ্গ ভাজক আছে। খেয়াল কর, একটি নিঃসঙ্গ ভাজকের ঠিক $K$
-সংখ্যক ভাজক থাকতে হবে। যদি একাধিক সমাধান থেকে থাকে তাহলে সবচেয়ে বড়ো সংখ্যাটি প্রিন্ট কর। আর যদি কোনো সমাধান না থেকে থাকে তাহলে প্রিন্ট করবে $-1$
।
ইনপুটের শুরুতে থাকবে একটি ধনাত্বক পূর্ণসংখ্যা $T$
($T \leq 10^6$
) যেটি হচ্ছে মোট টেস্ট কেসের সংখ্যা। প্রতিটি টেস্ট কেসে থাকবে তিনটি ধনাত্নক পূর্ণসংখ্যা, সীমা নির্দেশকারী $L, R$
($1 \leq L \leq R \leq 10^5$
) এবং $K$
($1 \leq K \leq 128$
)।
ইনপুট অনেক বড়ো হবে, তাই দ্রুততর ইনপুট/আউটপুট I/O ব্যবহার করো।
প্রতিটি টেস্ট কেসের জন্য বৃহত্তম নিঃসঙ্গ ভাজক বিশিষ্ট সংখ্যাটি প্রিন্ট কর। এরপরে স্পেস দিয়ে নিঃসঙ্গ ভাজকটি প্রিন্ট কর।
খেয়াল কর, একাধিক সমাধান থাকলে সর্বোচ্চ সংখ্যাটি প্রিন্ট করবে। আর কোনো সমাধান না থাকলে $-1$
প্রিন্ট করবে। বিস্তারিত বোঝার জন্য নমুনা ইনপুট/আউটপুট দেখ।
Input | Output |
---|---|
3 1 6 2 1 8 3 1 10 5 | 5 5 8 4 -1 |
প্রথম কেস: $3$
টি পূর্ণসংখ্যা $2, 3$
and $5$
-এর একটি করে নিঃসঙ্গ ভাজক আছে যার ঠিক $2$
টি ভাজক আছে. $5$
-এর আছে সর্বোচ্চ নিঃসঙ্গ ভাজক যেটি হল $5$
। সুতরাং উত্ত হবে $5$
। খেয়াল কর, $6$
-এরও কিন্তু দুটি ভাজক $2$
ও $3$
আছে যাদের ঠিক $2$
টি ভাজক আছে। কিন্তু এরা নিঃসঙ্গ নয়।
দ্বিতীয় কেস: এই সীমার মধ্যে শুধু $4$
-এরই $3$
টি ভাজক আছে। আবার, $4$
শুধু নিজের ভাজকই নয়, এটি $8$
-এরও ভাজক। ফলে, $4$
ও $8$
দুটি সংখ্যারই মাত্র একটি ভাজক আছে যার ঠিক $3$
টি ভাজক আছে। সুতরাং সম্ভাব্য উত্তর হবে, $4$
অথবা $8$
। যেহেতু এখানে একাধিক সমাধান আছে তাই আমরা সর্বোচ্চটি বেছে নেব। সুতরাং উত্তর হবে, $8$
।
তৃতীয় কেস: এই সীমার মধ্যে এমন কোনো ভাজক নেই যার $5$
টি ভাজক আছে।