核心:最大公约数的复习
小技巧最后两位一定是99
满分代码, 从个位9开始, res存储数据
排过序后,第三个测试点能通过,记住, 一定要排序
/**
这题实在是太经典了
题意: A和A+1的所有数字之和是a,b
a,b间的最大公约数是质数
小技巧:可以冲100开始,最后两位一定是99,才可能有最大公约数
数学分析:
m : 8位9,一个8 最大80
n: m + 1 最大是81
计算90以内m、n公共最大除数，该除数是大于2的质数
则m+1必须进位,否则无结果,如同80和81(仔细想下即可)
条件转化1: 进位等价于计算m以多少个数字9结尾
条件转化2: x个9结尾，则有(m-n+1)%9==0
条件2推导:
从而m的个位必然为9。
若m的十位数不是9，而个位9，则n=m-8
百位非9，个十为9，则n=m-17
以此类推，n=m+1-t*9，t为末位连续9的个数
最小差值: 17，即以99结尾
所以最后两位一定是99
*/
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
struct node{
int d; int v;
bool operator< (const node& t) const
{
if(d != t.d) return d < t.d;
else return v < t.v;
}
};
vector<node> res;
bool is_prime(int x)
{
if (x <= 2) return false;
for(int i = 2; i <= x / i; i++)
{
if (x % i == 0) return false;
}
return true;
}
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int getsum(int x)
{
int sumx = 0;
while (x)
{
sumx += x % 10;
x /= 10;
}
return sumx;
}
int main()
{
int limit;
cin >> limit;
for(int j = 1; j <= limit; j++)
{
printf("Case %d\n", j);
res.clear();
int k, m, n = 0, t;
cin >> k >> m;
int mins = pow(10, k - 1), maxs = pow(10.0, k), adds = 10;
mins += adds - 1;
bool flag = true;
for(int i = mins, cnt = 0; i < maxs; i += adds)
{
if (getsum(i) == m)
{
n = getsum(i + 1);
if (is_prime(gcd(m, n)))
{
flag = false;
res.push_back({n, i});
}
}
}
if (flag) printf("No Solution\n");
else{
sort(res.begin(), res.end());
for(auto &t: res) printf("%d %d\n", t.d, t.v);
}
}
}
17分 代码 测试点3错误
排了序也不行,应该是漏数据了
/**
这题实在是太经典了
题意: A和A+1的所有数字之和是a,b
a,b间的最大公约数是质数
小技巧:可以冲100开始,最后两位一定是99,才可能有最大公约数
数学分析:
m : 8位9,一个8 最大80
n: m + 1 最大是81
计算90以内m、n公共最大除数，该除数是大于2的质数
则m+1必须进位,否则无结果,如同80和81(仔细想下即可)
条件转化1: 进位等价于计算m以多少个数字9结尾
条件转化2: x个9结尾，则有(m-n+1)%9==0
条件2推导:
从而m的个位必然为9。
若m的十位数不是9，而个位9，则n=m-8
百位非9，个十为9，则n=m-17
以此类推，n=m+1-t*9，t为末位连续9的个数
最小差值: 17，即以99结尾
所以最后两位一定是99
*/
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
bool is_prime(int x)
{
if (x <= 2) return false;
for(int i = 2; i <= x / i; i++)
{
if (x % i == 0) return false;
}
return true;
}
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int getsum(int x)
{
int sumx = 0;
while (x)
{
sumx += x % 10;
x /= 10;
}
return sumx;
}
int main()
{
int limit;
cin >> limit;
for(int j = 1; j <= limit; j++)
{
printf("Case %d\n", j);
int k, m, n = 0, t;
cin >> k >> m;
// 较难点:找最小有几位9, 公式 n = m +1 - t*9;
for(t = 1; t < k; t++)
{
n = m + 1 - t * 9;
if (is_prime(gcd(m, n))) break;
}
int mins = pow(10.0, k - 1), maxs = pow(10.0, k), adds = pow(10.0, t);
mins += adds - 1;
bool flag = true;
for(int i = mins, cnt = 0; i < maxs; i += adds)
{
if (cnt % 10 == 9) //过滤掉高位是9
{
cnt++;
continue;
}
if (getsum(i) == m)
{
flag = false;
printf("%d %d\n", n, i);
}
cnt++;
}
if (flag) printf("No Solution\n");
}
}
加入排序 17分
/**
这题实在是太经典了
题意: A和A+1的所有数字之和是a,b
a,b间的最大公约数是质数
小技巧:可以冲100开始,最后两位一定是99,才可能有最大公约数
数学分析:
m : 8位9,一个8 最大80
n: m + 1 最大是81
计算90以内m、n公共最大除数，该除数是大于2的质数
则m+1必须进位,否则无结果,如同80和81(仔细想下即可)
条件转化1: 进位等价于计算m以多少个数字9结尾
条件转化2: x个9结尾，则有(m-n+1)%9==0
条件2推导:
从而m的个位必然为9。
若m的十位数不是9，而个位9，则n=m-8
百位非9，个十为9，则n=m-17
以此类推，n=m+1-t*9，t为末位连续9的个数
最小差值: 17，即以99结尾
所以最后两位一定是99
*/
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
bool is_prime(int x)
{
if (x <= 2) return false;
for(int i = 2; i <= x / i; i++)
{
if (x % i == 0) return false;
}
return true;
}
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int getsum(int x)
{
int sumx = 0;
while (x)
{
sumx += x % 10;
x /= 10;
}
return sumx;
}
struct node{
int d; int v;
bool operator< (const node& t) const {
if (d != t.d) return d < t.d;
else return v < t.v;
}
};
int main()
{
int limit;
cin >> limit;
for(int j = 1; j <= limit; j++)
{
printf("Case %d\n", j);
int k, m, n = 0, t;
cin >> k >> m;
// 较难点:找最小有几位9, 公式 n = m +1 - t*9;
int mins = pow(10.0, k - 1), maxs = pow(10.0, k), adds;
bool flag = true;
vector<node> res;
for(t = 1; t < k; t++)
{
n = m + 1 - t * 9;
if (!is_prime(gcd(m, n))) continue;
adds = pow(10.0, t);
mins += adds - 1;
for(int i = mins, cnt = 0; i < maxs; i += adds)
{
if (cnt % 10 == 9) //过滤掉高位是9
{
cnt++;
continue;
}
if (getsum(i) == m)
{
flag = false;
res.push_back({n, i});
}
cnt++;
}
}
if (flag) printf("No Solution\n");
else
{
sort(res.begin(), res.end());
for(auto &r: res) printf("%d %d\n", r.d, r.v);
}
}
}
0分 4个错误
#include <cstring>
#include <iostream>
#include <math.h>
using namespace std;
const int N = 110;
int getnum(int x)
{
int sum = 0;
while (x)
{
sum += x % 10;
x /= 10;
}
return sum;
}
int gcd(int x, int y)
{
return y ? gcd(y, x % y) : x;
}
bool check(int x)
{
if (x <= 2) return false;
for(int i = 2; i < x / i; i++)
{
if (x % i == 0) return false;
}
return true;
}
int main()
{
int cnt, k, m, n, num;
cin >> cnt;
for(int i = 1; i <= cnt; i++)
{
cin >> k >> m;
int x = pow(10, k - 3);
int y = x * 10 - 1;
bool f = false;
printf("Case %d\n", i);
for(int i = x; i <= y; i++)
{
num = i * 100 + 99;
//printf("%d %d\n", num, getnum(num));
if (getnum(num) == m)
{
n = getnum(num + 1);
int c = gcd(m, n);
if (check(c))
{
f = true;
printf("%d %d\n", n, num);
}
}
}
if (!f) puts("No solution\n");
}
}
17分代码 测试点3错哦
#include <iostream>
#include <cstring>
#include <math.h>
using namespace std;
const int num = 100;
int gcd(int a, int b)
{
if (b == 0) return a;
else return gcd(b, a % b);
}
int getsum(int x)
{
int total = 0;
while (x)
{
total += x % 10;
x /= 10;
}
return total;
}
bool is_prime(int x)
{
if (x <= 2) return false;
for(int i = 2; i * i <= x; i++)
{
if (x % i == 0) return false;
}
return true;
}
// 这题的题目十分容易读错,用了of的定语
// the sum of all the digits of A+1 is n; 指 A + 1 = X, X的每一位和是n
int main()
{
int m;
cin >> m;
for(int i = 1; i <= m; i++)
{
int k, n;
cin >> k >> n;
k -= 2;
printf("Case %d\n", i);
int length = pow(10, k) - 1;
bool flag = false;
for(int j = 1; j <= length; j++) {
int left = j * num;
int right = num - 1;
int x = left + right;
if (getsum(x) == n) {
int y = x + 1;
int b = getsum(y);
int z = gcd(n, b);
if (is_prime(z)) printf("%d %d\n", b, x), flag = true;
}
}
if (!flag) printf("No Solution\n");
}
}
