第八届“图灵杯”NEUQ-ACM程序设计竞赛个人赛 I 买花
题目描述:
情人节马上要到了,阳阳想送出n朵花给喜欢的妹妹,他打算提前开始买。但是,因为他有强迫症,所有的花要分k天买(k>1,即不能一天全买完),第一天他可以买任意朵花,之后每一天买花的数量为前一天的两倍,(如若第一天买4朵,第二天就要买8朵,以此类推)。
现在离情人节还有15天(k≤15),请你告诉阳阳,他能不能刚好买到n朵花。
输入描述:
多组输入。第一行一个正整数T(1<=T<=10^5),表示数据组数。
接下来T行,每行一个正整数n(1<=n<=10^9),表示预计买花的数量。
输出描述:
每组数据输出一行,共T行。
判断能否刚好买到n朵花,可以则输出"YE5",否则输出"N0"。
示例:
输入:
2 21 20
输出:
YE5 N0
这道初中数学题道题对公式优化一下就可以了,这也算本小白在牛客的第一道题了吧,dalao勿喷。
首先这是个等比数列求和,把模型搞出来:
然后遍历每一个ks是否存在一个整数 带入上式能够成立。我一开始的思路是对k和 都进行遍历,显然TLE了。
于是我抖了个机灵,直接判断 能否整除 ,再优化一下就是用 来替换上式,位运算会更快些。
代码:
#include<iostream> #include<string> #include<cstring> #include<algorithm> #include<cmath> #include<vector> using namespace std; int main() { long long t; cin>>t; while(t--) { long long n; long long judge = 0; cin>>n; for(long long k = 2;k <= 15;k++) { if(n % ((1<<k) - 1) == 0) { judge = 1; break; } } if(judge) { cout<<"YE5"<<endl; } else { cout<<"N0"<<endl; } } return 0; }