Uncle Johny
题目链接：
水题。排序即可
代码如下：
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 typedef struct{ 8 int pos, val; 9 }aa;10 11 aa a[1010];12 13 bool cmp(aa x,aa y)14 {15 return x.val
Missing some chairs
题目链接：
计算2^n - 1。快速模幂
代码如下：
1 #include2 #include 3 #include 4 #define MOD 1000000000+7 5 using namespace std; 6 7 long long a_b_MOD_c(long long a, long long b, long long c) 8 { 9 if(b==1)10 return a%c;11 long long temp = a_b_MOD_c(a, b/2, c);12 if(b%2 == 1)13 return (temp*temp*a)%c;14 else15 return (temp*temp)%c;16 }17 18 int main()19 {20 // freopen("in.txt", "r", stdin);21 22 int T;23 long long n;24 scanf("%d", &T);25 while(T--){26 scanf("%lld", &n);27 printf("%lld\n", a_b_MOD_c(2,n,MOD)-1);28 }29 return 0;30 }
Square Digit Squares
题目链接：
找到1-1e10之间的平方数并且只含有0.1.4.9
暴力枚举平方数，打表即可
代码如下：
1 #include2 #include 3 #include 4 #include 5 #include 6 #define ll long long 7 using namespace std; 8 9 int tag[600000], sum[600000];10 11 bool Judge(ll n)12 {13 while(n){14 if(n%10==0 || n%10==1 || n%10==4 || n%10==9);15 else return false;16 n/=10;17 }18 return true;19 }20 21 int main()22 {23 // freopen("in.txt", "r" , stdin);24 25 int T;26 ll a, b;27 memset(tag, 0, sizeof tag);28 memset(sum, 0, sizeof sum);29 for(ll i=1; i<100100; i++){30 if(Judge(i*i)){31 tag[i] = 1;32 }33 sum[i] = sum[i-1]+tag[i];34 }35 scanf("%d", &T);36 while(T--)37 {38 scanf("%lld%lld", &a, &b);39 int temp = (sqrt(a)-(int)sqrt(a))==0?1:0;40 int ans = sum[(int)sqrt(b)] - sum[(int)sqrt(a)-temp];41 printf("%d\n", ans);42 }43 return 0;44 }
Superpowers of 2
题目链接：
也是快速模幂，数据卡的比较死一定要用unsigned long long才行，最后平方一定要分开做
代码如下：
1 #include2 #include 3 #include 4 #include 5 #define ll unsigned long long 6 #define MOD 1000000000+7 7 using namespace std; 8 9 ll a_b_MOD_c(ll a, ll b, ll c)10 {11 ll product = a,ans = 1;12 while(b)13 {14 if(b&1==1){15 ans *= product;16 ans %= c;17 }18 b>>=1;19 product = (product*product)%c;20 }21 return ans;22 }23 24 ll Change(ll n)25 {26 int dig[1000], top = 0;27 while(n){28 dig[top++] = (n&1)?1:0;29 n>>=1;30 }31 ll ret = 0;32 for(int i=top-1; i>=0; i--){33 ret += dig[i]==1?1:0;34 if(i!=0)ret*=10;35 }36 return ret;37 }38 39 int main()40 {41 // freopen("in.txt", "r" , stdin);42 43 int T;44 ll n;45 scanf("%d", &T);46 while(T--)47 {48 scanf("%llu", &n);49 ll ans = a_b_MOD_c(2, Change(n), MOD);50 ans = a_b_MOD_c(ans, 2, MOD);51 printf("%llu\n", ans);52 }53 return 0;54 }