Goodbye-2017 div2比赛整理

  1. A-幸运数
  2. B-sumoon的一天
  3. C-第K个因子

2017年12月24日,圣诞节前一天。是个整理题的好日子。

A-幸运数

Description

世界上有很多人都有不同的习惯。
比如,13”这个数字被西方的一些国家和民族视为不吉利的凶数。4这个数字被很多亚洲人认为是不吉利的数。
北方的小红红就不太喜欢“7”这个数字,她认为如果一个正整数能被7整除,或者这个数的某一位有7,这个数就不是一个吉利的数。比如71,十位上有7这个数字,所以71是不吉利数字。再比如14能被7整除,14也不是吉利数字。现在问题来了,小红红想知道小于N的所有吉利数的平方和,你能帮助小红红解决这个问题吗?

例如:N = 8,<= 8与7无关的数包括:1 2 3 4 5 6 8,平方和为:1+4+9+16+25+36+64=155。

Input

输入:
第一行:输入一个N,代表输入的测试样例的个数。
接下来的2-N+1行,每行有一个M。
1<=N<1001,1 <= M< 10^6+1

Output

输出:
共N行,每行一个数,对应N个测试的计算结果。

Sample Input 1:
4
4
2
1
6

Sample Output 1:
30
5
1
91


这个题思路不难,但是数比较大,很容易超时。
但也是我这个从未参加过竞赛的菜鸡第一次正式接触到打表这个骚操作😳

12.25重写

1
2
3
4
5
6
7
8
9
10
11
int k = 7;
for (int i = 1; i<MAX ; i *= 10)//控制数位
{
for(int j = 0;j*10 < MAX;j+=i)//比7高位数的处理
{
for (int l = 0; l < i; l++)//当7不是个位时遍历个位
{
printf("%d ",j*10+k*i+l);
}
}
}

所以思路就是用一个数组筛除不符合题意的数,并挨个算出到某一点的平方和。
题解写的很棒,mark

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
void init()
{
memset(luck, true, sizeof(luck));
for (int i = 7; i < MAXN; i += 7)
{
luck[i] = false;
}

int r;
for (int i = 1; i < MAXN; i *= 10)
{
r = i * 10;
for (int j = i * 7; j < MAXN; j += r)
{
for (int k = 0; k < i; k++)
{
luck[k + j] = false;
}
}
}
return ;
}
void solve()
{
sum[0] = 0;
sum[1] = 1;
for (long long i = 2; i < MAXN; i++)
{
if (luck[i])
{
sum[i] = sum[i - 1] + i * i;
}
else
{
sum[i] = sum[i - 1];
}
}
return ;
}

B-sumoon的一天

Description

sumoon得到了很多的糖果,所以他决定从A镇到C镇去卖糖果。在路上,他看见了两个小朋友在地上画圆。他决定给定两个圆心分别为(x1,y1),(x2,y2),半径分别为r1和r2。如果两圆相交或者相切。那么就会就小孩糖果吃。

Input

单组测试

第一行:第一个圆的圆心x1,y1,和半径r1(-100<=x1,y1<=100 , 0<r1<100)

第二行:第二个圆的圆心x2,y2,和半径r2(-100<=x2,y2<=100 , 0<r2<100)

坐标和半径均为整数

Output
如果小孩能吃到糖那么输出 YES ,其他情况输出NO。

Sample Input 1 :
1 1 1
-1 1 1

Sample Output 1 :
YES

Sample Input 2 :
1 1 1
-1 -1 1

Sample Output 2 :
NO

圆相切或相交就是排除掉内含与圆外不相交

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
int main(){
int x1,y1,r1,x2,y2,r2;
scanf("%d %d %d",&x1,&y1,&r1);
getchar();
scanf("%d %d %d",&x2,&y2,&r2);
int x = (x1 - x2);
int y = (y1 - y2);
int r = r1 + r2;
int rr = r1 - r2;
if (x*x + y*y <= r*r && x*x + y*y >= rr*rr)
{
printf("YES");
}
else printf("NO");

return 0;
}

C-第K个因子

Description
给你两个数 N 和 k ,请你求出 N 的因子中第k小的那个。

Input

第一行一个整数 T 表示一共有T组测试数据,接下来T行每行两个整数 N 和 k(1≤ T ≤50,1 ≤ n ≤ 10^15, 1 ≤ k ≤ 10^9)

Output

输出T行,每行一个整数,表示N的第k小的因子,如果不存在第k小因子,请输出-1

Sample Input 1 :
3
4 2
5 3
12 5

Sample Output 1 :
2
-1
6

10^15这样大的数如果挨个遍历一遍(O(n))肯定会超时。
所以可以只遍历到sqrt(n)的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
long long the_k_factor(long long n, long long k)
{
int j = 0,t = 0,count = 0;
for (long long int i = 1; i <= sqrt(n); i++) {
if (n % i == 0) {
long long large = n/i;
a[j++] = i;
if (i != large)
b[t++] = large;
count++;
if (k == count)
break;
}
}

if (k <= 0 || k > j + t)
return -1;
if (k <= j)
return a[k-1];
else
return b[t-(k-j)];
}
script>