문제
길고 얇은 막대를 만드는 과정은 다음과 같습니다.
- 기본으로 사용할 막대를 고릅니다. 사용 가능한 막대의 길이는 $A_1, \cdots, A_N$입니다.
- 원하는 길이가 될 때까지 0ドル$번 이상 막대를 늘립니다. 기계에 2ドル$ 이상의 양의 정수 $k$를 설정해서 막대를 넣으면, 길이가 $x$였던 막대가 길이 $kx$의 막대가 됩니다.
주어진 $Q$개의 길이 각각에 대해 길이가 $L_i$인 막대를 만드는 방법의 수를 출력하세요. 두 방법이 서로 다르다는 것은 처음 선택한 막대가 다르거나, 막대를 늘리는 과정에서 입력한 정수 $k$의 수열이 서로 다르다는 것을 의미합니다.
출력
첫 줄에 $Q$개의 수를 공백으로 구분해 출력합니다. $i$번째 수는 길이가 $L_i$인 막대를 만드는 방법의 수입니다. 가능한 모든 입력에 대해 답이 10ドル^9$을 넘지 않음을 증명할 수 있습니다.
길이 6ドル$인 막대를 만드는 서로 다른 방법은 다음과 같습니다.
- 길이가 1ドル$인 막대를 고릅니다. 길이를 2ドル$배 늘려 길이를 2ドル$로 만듭니다. 길이를 3ドル$배 늘려 길이를 6ドル$으로 만듭니다.
- 길이가 1ドル$인 막대를 고릅니다. 길이를 3ドル$배 늘려 길이를 3ドル$로 만듭니다. 길이를 2ドル$배 늘려 길이를 6ドル$으로 만듭니다.
- 길이가 1ドル$인 막대를 고릅니다. 길이를 6ドル$배 늘려 길이를 6ドル$으로 만듭니다.
- 길이가 2ドル$인 막대를 고릅니다. 길이를 3ドル$배 늘려 길이를 6ドル$으로 만듭니다.
- 길이가 3ドル$인 막대를 고릅니다. 길이를 2ドル$배 늘려 길이를 6ドル$으로 만듭니다.
W3sicHJvYmxlbV9pZCI6IjI4NDM3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViOWM5XHViMzAwIFx1YjljY1x1YjRlNFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+XHVhZTM4XHVhY2UwIFx1YzU4N1x1Yzc0MCBcdWI5YzlcdWIzMDBcdWI5N2MgXHViOWNjXHViNGRjXHViMjk0IFx1YWNmY1x1YzgxNVx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjMmI1XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YWUzMFx1YmNmOFx1YzczY1x1Yjg1YyBcdWMwYWNcdWM2YTlcdWQ1NjAgXHViOWM5XHViMzAwXHViOTdjIFx1YWNlMFx1Yjk4NVx1YjJjOFx1YjJlNC4gXHVjMGFjXHVjNmE5IFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWI5YzlcdWIzMDBcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0ICRBXzEsIFxcY2RvdHMsIEFfTiRcdWM3ODVcdWIyYzhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzZkMFx1ZDU1OFx1YjI5NCBcdWFlMzhcdWM3NzRcdWFjMDAgXHViNDIwIFx1YjU0Y1x1YWU0Y1x1YzljMCAkMCRcdWJjODggXHVjNzc0XHVjMGMxIFx1YjljOVx1YjMwMFx1Yjk3YyBcdWIyOThcdWI5YmRcdWIyYzhcdWIyZTQuIFx1YWUzMFx1YWNjNFx1YzVkMCAkMiQgXHVjNzc0XHVjMGMxXHVjNzU4IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggJGskXHViOTdjIFx1YzEyNFx1YzgxNVx1ZDU3NFx1YzExYyBcdWI5YzlcdWIzMDBcdWI5N2MgXHViMTIzXHVjNzNjXHViYTc0LCBcdWFlMzhcdWM3NzRcdWFjMDAgJHgkXHVjNjAwXHViMzU4IFx1YjljOVx1YjMwMFx1YWMwMCBcdWFlMzhcdWM3NzQgJGt4JFx1Yzc1OCBcdWI5YzlcdWIzMDBcdWFjMDAgXHViNDI5XHViMmM4XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzhmY1x1YzViNFx1YzljNCAkUSRcdWFjMWNcdWM3NTggXHVhZTM4XHVjNzc0IFx1YWMwMVx1YWMwMVx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVhZTM4XHVjNzc0XHVhYzAwICRMX2kkXHVjNzc4IFx1YjljOVx1YjMwMFx1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWMxMzhcdWM2OTQuIFx1YjQ1MCBcdWJjMjlcdWJjOTVcdWM3NzQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3NFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDAgXHVjYzk4XHVjNzRjIFx1YzEyMFx1ZDBkZFx1ZDU1YyBcdWI5YzlcdWIzMDBcdWFjMDAgXHViMmU0XHViOTc0XHVhYzcwXHViMDk4LCBcdWI5YzlcdWIzMDBcdWI5N2MgXHViMjk4XHViOWFjXHViMjk0IFx1YWNmY1x1YzgxNVx1YzVkMFx1YzExYyBcdWM3ODVcdWI4MjVcdWQ1NWMgXHVjODE1XHVjMjE4ICRrJFx1Yzc1OCBcdWMyMThcdWM1ZjRcdWM3NzQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3NFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTY5XHViMmM4XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWI5YzlcdWIzMDBcdWM3NTggXHVhYzFjXHVjMjE4ICROJFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuICQoMSBcXGxlIE4gXFxsZSAxMDBcXCwwMDApJDxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwICROJFx1YWMxY1x1Yzc1OCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YzgxNVx1YzIxOCAkQV8xLCBBXzIsIFxcY2RvdHMsIEFfTiRcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuICQoMSBcXGxlIEFfaSBcXGxlIDEwMFxcLDAwMCkkPFwvcD5cclxuXHJcbjxwPlx1YzE0Ylx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViOWNjXHViNGU0XHVhY2UwXHVjNzkwIFx1ZDU1OFx1YjI5NCBcdWI5YzlcdWIzMDAgXHVhZTM4XHVjNzc0XHVjNzU4IFx1YWMxY1x1YzIxOCAkUSRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LiAkKDEgXFxsZSBRIFxcbGUgMTAwXFwsMDAwKSQ8XC9wPlxyXG5cclxuPHA+XHViMTM3XHVjOWY4IFx1YzkwNFx1YzVkMCAkUSRcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4ICRMXzEsIFxcY2RvdHMsIExfUSRcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuICQoMSBcXGxlIExfaSBcXGxlIDEwMFxcLDAwMCkkPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCAkUSRcdWFjMWNcdWM3NTggXHVjMjE4XHViOTdjIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NzQgXHVjZDljXHViODI1XHVkNTY5XHViMmM4XHViMmU0LiAkaSRcdWJjODhcdWM5ZjggXHVjMjE4XHViMjk0IFx1YWUzOFx1Yzc3NFx1YWMwMCAkTF9pJFx1Yzc3OCBcdWI5YzlcdWIzMDBcdWI5N2MgXHViOWNjXHViNGRjXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWM3ODVcdWIyYzhcdWIyZTQuIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWJhYThcdWI0ZTAgXHVjNzg1XHViODI1XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWIyZjVcdWM3NzQgJDEwXjkkXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWM3NGNcdWM3NDQgXHVjOTlkXHViYTg1XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWMyYjVcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPlx1YWUzOFx1Yzc3NCAkNiRcdWM3NzggXHViOWM5XHViMzAwXHViOTdjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjMmI1XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YWUzOFx1Yzc3NFx1YWMwMCAkMSRcdWM3NzggXHViOWM5XHViMzAwXHViOTdjIFx1YWNlMFx1Yjk4NVx1YjJjOFx1YjJlNC4gXHVhZTM4XHVjNzc0XHViOTdjICQyJFx1YmMzMCBcdWIyOThcdWI4MjQgXHVhZTM4XHVjNzc0XHViOTdjICQyJFx1Yjg1YyBcdWI5Y2NcdWI0ZWRcdWIyYzhcdWIyZTQuIFx1YWUzOFx1Yzc3NFx1Yjk3YyAkMyRcdWJjMzAgXHViMjk4XHViODI0IFx1YWUzOFx1Yzc3NFx1Yjk3YyAkNiRcdWM3M2NcdWI4NWMgXHViOWNjXHViNGVkXHViMmM4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWFlMzhcdWM3NzRcdWFjMDAgJDEkXHVjNzc4IFx1YjljOVx1YjMwMFx1Yjk3YyBcdWFjZTBcdWI5ODVcdWIyYzhcdWIyZTQuIFx1YWUzOFx1Yzc3NFx1Yjk3YyAkMyRcdWJjMzAgXHViMjk4XHViODI0IFx1YWUzOFx1Yzc3NFx1Yjk3YyAkMyRcdWI4NWMgXHViOWNjXHViNGVkXHViMmM4XHViMmU0LiBcdWFlMzhcdWM3NzRcdWI5N2MgJDIkXHViYzMwIFx1YjI5OFx1YjgyNCBcdWFlMzhcdWM3NzRcdWI5N2MgJDYkXHVjNzNjXHViODVjIFx1YjljY1x1YjRlZFx1YjJjOFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVhZTM4XHVjNzc0XHVhYzAwICQxJFx1Yzc3OCBcdWI5YzlcdWIzMDBcdWI5N2MgXHVhY2UwXHViOTg1XHViMmM4XHViMmU0LiBcdWFlMzhcdWM3NzRcdWI5N2MgJDYkXHViYzMwIFx1YjI5OFx1YjgyNCBcdWFlMzhcdWM3NzRcdWI5N2MgJDYkXHVjNzNjXHViODVjIFx1YjljY1x1YjRlZFx1YjJjOFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVhZTM4XHVjNzc0XHVhYzAwICQyJFx1Yzc3OCBcdWI5YzlcdWIzMDBcdWI5N2MgXHVhY2UwXHViOTg1XHViMmM4XHViMmU0LiBcdWFlMzhcdWM3NzRcdWI5N2MgJDMkXHViYzMwIFx1YjI5OFx1YjgyNCBcdWFlMzhcdWM3NzRcdWI5N2MgJDYkXHVjNzNjXHViODVjIFx1YjljY1x1YjRlZFx1YjJjOFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVhZTM4XHVjNzc0XHVhYzAwICQzJFx1Yzc3OCBcdWI5YzlcdWIzMDBcdWI5N2MgXHVhY2UwXHViOTg1XHViMmM4XHViMmU0LiBcdWFlMzhcdWM3NzRcdWI5N2MgJDIkXHViYzMwIFx1YjI5OFx1YjgyNCBcdWFlMzhcdWM3NzRcdWI5N2MgJDYkXHVjNzNjXHViODVjIFx1YjljY1x1YjRlZFx1YjJjOFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjI4NDM3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTWFraW5nIFN0aWNrcyIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIHByb2Nlc3Mgb2YgbWFraW5nIGxvbmcsIHRoaW4gc3RpY2tzIGlzIGFzIGZvbGxvd3M6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+WW91IHNlbGVjdCBhIHN0aWNrIHRvIHVzZSBhcyBhIGJhc2UgYmFja2JvbmUuIFRoZSBhdmFpbGFibGUgc3RpY2sgbGVuZ3RocyBhcmUgJEFfMSwgXFxjZG90cywgQV9OJC48XC9saT5cclxuXHQ8bGk+WW91IGV4dGVuZCB0aGUgc3RpY2sgJDAkIG9yIG1vcmUgdGltZXMsIHVudGlsIGl0IHJlYWNoZXMgdGhlIGRlc2lyZWQgbGVuZ3RoLiBJZiB5b3UgZW50ZXIgYSBwb3NpdGl2ZSBpbnRlZ2VyICRrJCBncmVhdGVyIHRoYW4gb3IgZXF1YWwgdG8gJDIkIHRvIHRoZSBtYWNoaW5lIGFuZCBpbnNlcnQgdGhlIHN0aWNrIGluIGEgbWFjaGluZSwgYSBzdGljayB3aXRoIGEgbGVuZ3RoIG9mICR4JCBiZWNvbWVzIGEgc3RpY2sgb2YgbGVuZ3RoICRreCQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Rm9yIGVhY2ggb2YgdGhlIGdpdmVuICRRJCBsZW5ndGhzLCBwcmludCB0aGUgbnVtYmVyIG9mIHdheXMgdG8gbWFrZSBhIHN0aWNrIG9mIGxlbmd0aCAkTF9pJC4gVHdvIG1ldGhvZHMgYXJlIGNvbnNpZGVyZWQgZGlmZmVyZW50IGlmIHRoZSBpbml0aWFsIHN0aWNrIHNlbGVjdGVkIGlzIGRpZmZlcmVudCBvciBpZiB0aGUgc2VxdWVuY2Ugb2YgaW50ZWdlcnMgJGskIGlucHV0IGluIHRoZSBwcm9jZXNzIG9mIGV4dGVuZGluZyB0aGUgc3RpY2sgZGlmZmVycy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBudW1iZXIgb2YgYmFzZSBzdGlja3MgJE4kLiAkKDEgXFxsZSBOIFxcbGUgMTAwXFwsMDAwKSQ8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zICROJCBkaWZmZXJlbnQgaW50ZWdlcnMgJEFfMSwgQV8yLCBcXGNkb3RzLCBBX04kLCBzZXBhcmF0ZWQgYnkgc3BhY2VzLiAkKDEgXFxsZSBBX2kgXFxsZSAxMDBcXCwwMDApJDxcL3A+XHJcblxyXG48cD5UaGUgdGhpcmQgbGluZSBjb250YWlucyB0aGUgbnVtYmVyIG9mIGRlc2lyZWQgc3RpY2sgbGVuZ3RocyAkUSQuICQoMSBcXGxlIFEgXFxsZSAxMDBcXCwwMDApJDxcL3A+XHJcblxyXG48cD5UaGUgZm91cnRoIGxpbmUgY29udGFpbnMgJFEkIGludGVnZXJzICRMXzEsIFxcY2RvdHMsIExfUSQsIHNlcGFyYXRlZCBieSBzcGFjZXMuICQoMSBcXGxlIExfaSBcXGxlIDEwMFxcLDAwMCkkPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgc2hvdWxkIG91dHB1dCAkUSQgbnVtYmVycywgc2VwYXJhdGVkIGJ5IHNwYWNlcy4gVGhlICRpJCYjMzk7dGggbnVtYmVyIGlzIHRoZSBudW1iZXIgb2Ygd2F5cyB0byBtYWtlIGEgc3RpY2sgb2YgbGVuZ3RoICRMX2kkLiBJdCBjYW4gYmUgcHJvdmVuIHRoYXQgdGhlIGFuc3dlciBkb2VzIG5vdCBleGNlZWQgJDEwXjkkIGZvciBhbGwgcG9zc2libGUgaW5wdXRzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+VGhlIGRpc3RpbmN0IHdheXMgdG8gbWFrZSBhIHN0aWNrIG9mIGxlbmd0aCAkNiQgYXJlIGFzIGZvbGxvd3M6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+U2VsZWN0IGEgc3RpY2sgb2YgbGVuZ3RoICQxJC4gSW5jcmVhc2UgaXRzIGxlbmd0aCBieSAkMiQgdGltZXMgdG8gbWFrZSBpdCAkMiQuIEluY3JlYXNlIGl0cyBsZW5ndGggYnkgJDMkIHRpbWVzIHRvIG1ha2UgaXQgJDYkLjxcL2xpPlxyXG5cdDxsaT5TZWxlY3QgYSBzdGljayBvZiBsZW5ndGggJDEkLiBJbmNyZWFzZSBpdHMgbGVuZ3RoIGJ5ICQzJCB0aW1lcyB0byBtYWtlIGl0ICQzJC4gSW5jcmVhc2UgaXRzIGxlbmd0aCBieSAkMiQgdGltZXMgdG8gbWFrZSBpdCAkNiQuPFwvbGk+XHJcblx0PGxpPlNlbGVjdCBhIHN0aWNrIG9mIGxlbmd0aCAkMSQuIEluY3JlYXNlIGl0cyBsZW5ndGggYnkgJDYkIHRpbWVzIHRvIG1ha2UgaXQgJDYkLjxcL2xpPlxyXG5cdDxsaT5TZWxlY3QgYSBzdGljayBvZiBsZW5ndGggJDIkLiBJbmNyZWFzZSBpdHMgbGVuZ3RoIGJ5ICQzJCB0aW1lcyB0byBtYWtlIGl0ICQ2JC48XC9saT5cclxuXHQ8bGk+U2VsZWN0IGEgc3RpY2sgb2YgbGVuZ3RoICQzJC4gSW5jcmVhc2UgaXRzIGxlbmd0aCBieSAkMiQgdGltZXMgdG8gbWFrZSBpdCAkNiQuPFwvbGk+XHJcbjxcL3VsPlxyXG4ifV0=