18290 校赛排名2

## 巡逻的士兵

#include<stdio.h>
#include<map>
using namespace std;
map<int,int>m;
int soilder(int count)
{
if(m.find(count)!=m.end()){
return m[count];
}
else
{
if(count <= 3)
return count == 3 ? 1 : 0;
else
{
if(count % 2 == 1)
return m[count]=soilder(count / 2) + soilder(count / 2 + 1);
else
return m[count]=2 * soilder(count / 2);
}
}
}
int main()
{
int n;
scanf(“%d”, &n);
while(n != 0)
{
printf(“%d\n”, soilder(n));
scanf(“%d”, &n);
}
}

# A  It is not ugly number

Time Limit:2000MS  Memory Limit:65535K

# 描述

```Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ...shows the
first 10 ugly numbers. By convention, 1 is included. Then, here are the first 10 Not ugly numbers:7, 11, 13, 14, 17, 19,
21, 22, 23, 26. Given the integer n, write a program to find and print the n'th Not ugly number.
```

# 输入格式

```First line is T（T<=10000）, the number of cases.
The T lines following. Each line of the input contains a positive integer n (n <= 100000000).
```

# 输出格式

```For each case, output the n'th Not ugly number .
```

```3
1
2
9
```

# 输出样例

```7
11
23```
```#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<set>
using namespace std;
typedef long long LL;
int main(){
int d={2,3,5},js=1,js2;
int i,j,k,n;
LL x,x2;
priority_queue<LL,vector<LL>,greater<LL> >pq;
set<LL>s;
vector<LL>l;
s.insert(1);
pq.push(1);
for(i=1;;i++){
x=pq.top();
l.push_back(x);
js++;
if(x>150000000)break;
pq.pop();
for(j=0;j<3;j++){
x2=x*d[j];
if(!s.count(x2)){
pq.push(x2);
s.insert(x2);
}
}
}
scanf("%d",&j);
while(j--)
{
scanf("%d",&n);
i=-1,js2=0;
while(i++,1)
{
js2+=l[i+1]-l[i]-1;
if(js2>=n) break;
}
printf("%lld\n",l[i+1]+n-js2-1);
}
return 0;
}
```

## 加密解密基础

base64

md5 32位 一般不可逆

abcdefg。。。。。xyz

def。。。。。。。abc

（ascii＋3）％26-》

tomorrow is friday

rot

rot5

5是偏移量，只对数字加密

rot13只对字母加密

rot18是把rot5和rot13一起用

rot47

vigenere

abcdef

rsa

des

ecc

ZIP伪加密

## rsa加密

rabin

n n的长度就是密文的长度

fai（n）＝。。。。。。

yafu分解n为p，q（p，q为素数）

m 明文

c密文 c＝。。。。。

## Ugly number

Write a program to find the `n`-th ugly number.

Ugly numbers are positive numbers whose prime factors only include `2, 3, 5`. For example, `1, 2, 3, 4, 5, 6, 8, 9, 10, 12` is the sequence of the first `10` ugly numbers.

Note that `1` is typically treated as an ugly number.

Hint:

1. The naive approach is to call `isUgly` for every number until you reach the nth one. Most numbers arenot ugly. Try to focus your effort on generating only the ugly ones.
2. An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.
3. The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: L1, L2, and L3.
4. Assume you have Uk, the kth ugly number. Then Uk+1 must be Min(L1 * 2, L2 * 3, L3 * 5).