CPU: 1s
Memory: 1024MB
রবিন হূড একটি সফল অভিযান সম্পন্ন করে ফিরে এসেছে। এখন সে শেরউড বনের N জন অধিবাসীদের ভিতরে স্বর্ণমুদ্রাগুলো বিলি করে দিতে চাইছে। এই কাজের সুবিধার জন্য সে তার K জন বিশ্বস্ত সহযোগীকে ডেকে পাঠালো।
এই K জন বিশ্বস্ত সহযোগীর আবার খেলাধুলার শখ। তারা N জন বাসিন্দাদেরকে একটি লাইনে দাঁড়া করালো এবং তাদের প্রত্যককে একটি পূর্ণসংখ্যা দিয়ে চিহ্নিত করল। তারপর তারা তাদেরকে স্বর্ণমুদ্রাগুলো দেয়া শুরু করল। একজন সহযোগী এসে তার প্রিয় পূর্ণসংখ্যা F চয়ন করে, যেখানে [1,100] এর মধ্যে থাকবে F এর মান। এরপর সে, F এর গুণিতকতম অবস্থানের লোকদেরকে একটি করে স্বর্ণমুদ্রা দেয়।
উদাহরণস্বরূপ, যদি দশজন বাসিন্দা এবং তিনজন সাহায্যকারী থাকে, যেখানে সাহায্যকারীদের প্রিয় সংখ্যা হচ্ছে {2,3,5}। তাহলে, প্রথম সাহায্যকারিী 2, 4, 6, 8, 10 নম্বর বাসিন্দাদের একটা করে স্বর্ণমুদ্রা প্রদান করবে। দ্বিতীয় সাহায্যকারী 3,6,9 তম বাসিন্দাকে স্বর্ণমুদ্রা দেবে। এরপর তৃতীয় সাহায্যকারী এসে ৫ এবং ১০ নম্বর লোককে দেবে।
এভাবে করে মূদ্রা বিতরণের পর তারা বাসিন্দাদের আনন্দের পরিমাণ বের করে। একজন ব্যক্তি তখনি আনন্দিত হবে, যখন সে অন্তত একটি স্বর্ণমুদ্রা পাবে। আর কেউ যদি কোন মুদ্রা না পায়, তাহলে সে সুখী হবে না।
রবিনহুড জানতে চায়, শেরউডের কতজন মানুষ আসলে সুখী। যেহেতু, সাহায্যকারীরা এখন পার্টি করায় ব্যস্ত, তোমারই রবিন হুডকে সাহায্য করতে হবে।
যদি বাসিন্দাদের সংখ্যা, সাহায্যকারীদের সংখ্যা এবং তাদের প্রত্যেকের প্রিয় সংখ্যা দেওয়া থাকে, তাহলে তোমাকে বলতে হবে যে খেলা শেষে কতজন মানুষ অসুখী থাকবে।
Robin Hood has just returned from a successful heist. He is now going to distribute gold coins among the N residents of Sherwood Forest. He asked K people from his band of “Merry Men” to help him with the task.
Since the K people are “Merry”, they decided to play a game. They first made the N residents stand in a line and assigned them integer id starting from 1. Then they started to distribute the coins in turn. A helper comes, and chooses his favorite integer number F, which is between [1,100]. Then the helper gives a single coin to each person standing at a position that is multiple of F.
For example, if there are 10 residents and 3 helpers, where each of the helper has favorite numbers {2,3,5}. Then in first turn, first helper gives person number 2, 4, 6, 8, 10 a single coin. The second helper gives person number 3,6,9 one coin. Then comes third helper and he gives person number 5 and 10 one coin.
So after distributing coins in such way, they determine happiness of the residents. A resident is said to be happy, if he has received at least one coin. Meaning, a person who did not receive any coin is unhappy.
Robin Hood wants to know how many people in Sherwood is unhappy. Since the “Merry Men” are partying after the game, he wants you to help him.
Given number of residents, number of helpers and favorite number of each of the helper, how many people are unhappy once the game ends?
ইনপুটের বর্ণনা
প্রথম লাইনে একটি ধনাত্মক পূর্ণসংখ্যা T ( T <= 100 ) দেওয়া থাকবে, যেটি টেস্টকেসের সংখ্যা নির্দেশ করে। এরপরের T কেসের শুরুতে দুইটি করে ধনাত্মক পূর্ণসংখ্যা N (N <= 10^16) এবং K (K <= 10) থাকবে। পরের লাইনে K সংখ্যক পূর্ণসংখ্যা থাকবে, যেগুলো হচ্ছে সাহায্যকারীদের প্রিয় সংখ্যা। সংখ্যাগুলোর মান ১ থেকে ১০০ এর ভিতরে থাকবে।
পয়েন্টের ব্যাখ্যা
১৫ পয়েন্টের জন্য N <= 100 এবং K = 1
২৫ পয়েন্টের জন্য N <= 10^5 এবং K <= 10
২৫ পয়েন্টের জন্য N <= 10^16 এবং K = 2
৩৫ পয়েন্টের জন্য N <= 10^16 এবং K <= 10
Input Specification
The first line contains a positive integer T ( T <= 100 ), number of test case. In the following T cases, there will be two positive integers N (N <= 10^16) and K (K <= 10). On the next line, there will be K integer, denoting the favorite numbers of K helpers between [1,100].
Point Distribution Subtask 1: 15 Points for N <= 100 and K = 1. Subtask 2: 25 Points for N <= 10^5 and K <= 10. Subtask 3: 25 Points for N <= 10^16 and K = 2. Subtask 4: 35 Points for N <= 10^16 and K <= 10.
আউটপুটের বর্ণনা
প্রতিটা টেস্টকেসের জন্য প্রথমে কেস সংখ্যা প্রিন্ট করার পর, শেরউডের অসুখী লোকের সংখ্যা বলতে হবে।
Output Specification
For each case print the case number and then number unhappy people in Sherwood.
Sample
| Input | Output |
|---|---|
| 3 10 1 3 10 2 2 3 10 3 2 3 5 | Case 1: 7 Case 2: 3 Case 3: 2 |
Explanation
In first case, there are 10 people in Sherwood. Person number {3,6,9} gets coin. So 7 people are unhappy.
In second case, out of 10 people {2,3,4,6,8,9,10} gets coin. {1,5,7} has 0 coins. So they are sad.
In third case, {2,3,4,5,6,8,9,10} gets coin. Only {1,7} are unhappy.
Problemsetter: Mohammad Samiul Islam