posted on 2021-06-02 20:59:42 | under 题解 | source
SP11198 是个神题，它考察了选手们的记忆、乱搞、找规律、压行能力。
本题题解是乱搞题解，没有证明。
下面就由我来解说一下：
第二问
重新读一下题，注意几个关键信息：
- \(\gcd(x,y)=1\)（互素）
- \(0<x,y\)（正整数）
- 有多少正整数不能表示为 \(ax+by\)？
好像什么时候做过？是的，这就是 P3951 [NOIP2017 提高组] 小凯的疑惑。所以，这一问答案是 \(x\times y-x-y\)。
第一问
好像没什么规律。
那我们写个程序看看：
//暴力求解第一问
//输出一个 1<=x,y<=10 的表格
#include <cstring>
#include <cstdio>
using namespace std;
bool vis[110];
int solve(int x,int y){//用 vis 标记能表示的数
memset(vis,0,sizeof vis);
for(int a=0;a<=y;a++){
for(int b=0;a*x+b*y<=x*y-x-y;b++){
vis[a*x+b*y]=1;
}
}
int ans=0;
for(int i=1;i<=x*y-x-y;i++) ans+=!vis[i];//统计不能表示的数
return ans;
}
int gcd(int a,int b){
return !b?a:gcd(b,a%b);
}
int n=10;
int main(){
printf(" ?");
for(int i=1;i<=n;i++) printf("%3d",i);//输出行号
//printf %3d 表示保留 3 位场宽
puts("");
for(int i=1;i<=n;i++){
printf("%2d",i);//输出列号
for(int j=1;j<=n;j++){
if(gcd(i,j)==1) printf("%3d",solve(i,j));
else printf(" ");//gcd!=1 就没有算的必要，都不合法
}
puts("");
}
return 0;
}
它的输出：
? 1 2 3 4 5 6 7 8 9 10
1 0 0 0 0 0 0 0 0 0 0
2 0 1 2 3 4
3 0 1 3 4 6 7 9
4 0 3 6 9 12
5 0 2 4 6 10 12 14 16
6 0 10 15
7 0 3 6 9 12 15 21 24 27
8 0 7 14 21 28
9 0 4 12 16 24 28 36
10 0 9 27 36
通过仔细观察，我们能找到一个规律：
\[\operatorname{solve}(i,j)=(i-1)\times (j-1)\div 2 \]怎么证明这个公式？我不会，也不需要会。
为了后面压行，我们把公式因式分解一下：
\[\operatorname{solve}(x,y)=[(x\times y-x-y)+1]\div 2 \]压行
英文题面有一句话：
O'Cearbhaill knew that neither the cydia store nor the app store has a decent text editor suitable for all programming languages, so he only accept programs less than equals to 100 characters in length.
大概就是说，你的代码长度必须 \(<100\;\texttt{B}\)。这也是你绑定了 SPOJ 账号却一直 waiting 的原因。
如果我们用 C++ 正常写，会写到 \(150\;\texttt{B}\)，甚至 \(200\;\texttt{B}\)。
所以我们不用 C++，用 C。
先了解几个 C 特性吧：
- 可以不
#include <stdio.h>就使用scanf/printf； int main中int可省略；main()里可以带参数当变量用，例如main(a,b,c)就是定义三个int变量叫 \(a,b,c\)，它们可以直接使用；return 0可省略；gets(s)中的 \(s\) 的类型可以不是char*。
根据这些，我们可以写出我们的第一个代码：
#define c (1LL*a*b-a-b)//当变量用，注意 1e8*1e8 会爆，要 *1LL
main(t,a,b){
scanf("%d",&t);
while(t--) scanf("%d%d",&a,&b),printf("%lld %lld\n",c+1>>1,c);
}
不太优秀，我们还可以：
- \(c\) 的那个括号可以不要；
- 删去换行和空格；
- 把
while改成for。
#define c 1LL*a*b-a-b
main(t,a,b){for(scanf("%d",&t);t--;scanf("%d%d",&a,&b),printf("%lld %lld\n",c+1>>1,c));}
还是不行。
我们不难发现一个问题：\(t\) 其实是没用的！把 \(t\) 吃掉，直接回答询问回答到 EOF 就行了！
#define c 1LL*a*b-a-b
main(a,b){for(scanf("%*d");~scanf("%d%d",&a,&b);printf("%lld %lld\n",c+1>>1,c));}
//scanf("%*d") 表示读入一个数字，并丢弃它
这样已经很接近 \(100\;\texttt{B}\) 了，但还是不行。
再想一下：吃掉 \(t\)，实际上就是吃掉 \(t\) 所在的那一行！所以可以换成 gets！
但好像没有 char* 给我们传参诶……
不要紧！上面说了 gets 的参数类型可以不是 char*，可以是 int* 啊！
直接传 &a 就好了！
#define c 1LL*a*b-a-b
main(a,b){for(gets(&a);~scanf("%d%d",&a,&b);printf("%lld %lld\n",c+1>>1,c));}
\(99\;\texttt{B}\)，可以 AC。
这道题就做完了，注意现在提交 SPOJ 的题需要绑定 SPOJ 的账号。
标签：int,题解,scanf,Testing,printf,SP11198,main,lld From： https://www.cnblogs.com/caijianhong/p/solution-SP11198.html