ওয়াল্ট এবং গাসের মধ্যে বড় রকমের ঝগড়া রয়েছে। সম্প্রতি গাস একটি ক্রিপ্টোগ্রাফিক সিস্টেম তৈরি করেছেন। ওয়াল্ট এটি ক্র্যাক করার চেষ্টা করছ্নে। চেষ্টা করার সময়, তিনি জানতে পেরেছেন যে ক্রিপ্টোগ্রাফিক সিস্টেমের অধীনে পূর্ণসংখ্যার একটি অ্যারে C রয়েছে। ওয়াল্টের অ্যারে C সম্পর্কে কিছু তথ্য দরকার।
ওয়াল্ট র্যান্ডম পূর্ণসংখ্যা সৃষ্টি করতে একটি অ্যালগরিদম তৈরি করেছেন । তিনি এই অ্যালগরিদম দ্বারা সৃষ্ট র্যান্ডম পূর্ণসংখ্যাগুলিকে "ক্রিপ্টো-নম্বর" হিসাবে অভিহিত করেন। অ্যালগরিদমটি নিম্নরূপ:
১. প্রথমে, "ক্রিপ্টো-নম্বর" = ** 1**।
২. ওয়াল্ট **1** এর চাইতে বড় দুটি পূর্ণসংখ্যা **r**, **p** এলোমেলোভাবে পছন্দ করেন । তারপরে তিনি **"ক্রিপ্টো নম্বর"** এর সাথে **rp** গুণ করেন ।
৩. গুণফলটি **"ক্রিপ্টো নম্বর"** এর নতুন মান ।
৪. তিনি ধাপ 2 এবং 3 পুনরাবৃত্তি করেন কিছু সময়ের জন্য ।
এটি গ্যারান্টিযুক্ত যে সৃষ্ট **"ক্রিপ্টো নম্বর"** এই সীমাবদ্ধতা অনুসরণ করে: ** 4 ≤ ক্রিপ্টো নম্বর ≤ 1012**।
এই অ্যালগরিদম ব্যবহার করে উদাহরণ দেখা যাকঃ
ধাপ 1: প্রথমে "ক্রিপ্টো নম্বর" = 1।
ধাপ 2: ধরা যাক, ওয়াল্ট যথাক্রমে 81, 3 - r, p এর মান হিসেবে নির্বাচন করলেন । গুণফল = 1 × 813 = 531441 ।
ধাপ 3: "ক্রিপ্টো নম্বর"-এর নতুন মান = 531441 ।
ওয়াল্ট যদি ধাপ 2 এবং 3 এর পুনরাবৃত্তি করেন তবে:
ধাপ 2: ধরা যাক, ওয়াল্ট এবার যথাক্রমে 6, 5 - r, p এর মান হিসেবে নির্বাচন করলেন । গুণফল = 531441 × 65 = 4132485216 ।
ধাপ 3: "ক্রিপ্টো নম্বর"-এর নতুন মান = 4132485216 ।
এবং এভাবে চলতে থাকবে ...
এখন ওয়াল্ট জানতে চান, একটি ক্রিপ্টো নম্বর k এর জন্য, অ্যারে C তে এমন কতগুলি পূর্ণসংখ্যা রয়েছে, যাদের দিয়ে k নিঃশেষে বিভাজ্য?
ইনপুটটির প্রথম লাইনে একটি পূর্ণসংখ্যা N, অ্যারের সাইজ C থাকে। পরের লাইনে N সংখ্যক স্পেস-বিভাজিত পূর্ণসংখ্যা Ci - অ্যারে C-র উপাদানগুলি থাকবে।
পরবর্তী লাইনে একটি পূর্ণসংখ্যা Q, কুয়েরীর সংখ্যা রয়েছে। পরবর্তী Q লাইনের প্রত্যেকটিতে একটি পূর্ণসংখ্যা K - "ক্রিপ্টো নম্বর" থাকবে।
সীমাবদ্ধতা:
1 ≤ N ≤ 106
1 ≤ Ci ≤ 1012
1 ≤ Q ≤ 104
4 ≤ k ≤ 1012
সাবটাস্ক ১, ১০ পয়েন্টের জন্য: 1 ≤ Q ≤ 10, 4 ≤ k ≤ 106
সাবটাস্ক ২, ৩০ পয়েন্টের জন্য: 1 ≤ Q ≤ 104, 4 ≤ k ≤ 106
সাবটাস্ক ৩, ৬০ পয়েন্টের জন্য: সম্পূর্ণ সীমাবদ্ধতা।
প্রতিটি কুয়েরীর জন্য, এই ফরম্যাটে একটি লাইনে প্রিন্ট করতে হবে (কোটেশন ব্যতীত): "Query x: y", যেখানে x কুয়েরী নং এবং y হল অ্যারে C তে এমন পূর্ণসংখ্যার সংখ্যা, যেসব পূর্ণসংখ্যা k কে নিঃশেষে বিভাজ্য করতে পারে ।
Input | Output |
---|---|
6 1 8 4 18 13 8 4 16 36 8 169 | Query 1: 4 Query 2: 3 Query 3: 4 Query 4: 2 |
In the first query, the integers in index 0, index 1, index 2 and index 5 in array completely divide 16. That is to say, the 4 integers in array : 1, 8, 4, 8 completely divide 16. |