#P1423. Optimus Prime

    ID: 157 传统题 1000ms 512MiB 尝试: 33 已通过: 7 难度: 9 上传者: 标签>CF2600省选/NOI-必胜/必败状态递推埃氏筛线性 DP同向双指针不变量分析

Optimus Prime

题目描述

两个人 A,B 玩游戏,A 先走,B 后走。 每次操作是任意选一个 1∼N1\sim N 中的数,再它累加到 CC 上,CC 的初值为 00。 加完后 CC 必须是质数,如果谁使得当前的 CC 不是质数则输掉。不妨认为 B 是天才一个,他的策略总是完美的。现在你要如何才能打败他。 例如 N=5N=5 时, 你可以选 33,则 C=3C=3, B可以选 22,C=5C=5, 你此时如果选 55,则 C=10C=10,你就输掉了。

输入格式

第一行一个数据 TT,T≤10000T≤10000 表示有 TT 组数据。 接下来每行一个整数 NN,1<N≤10001<N≤1000。

输出格式

针对每个数据,如果 B 获胜则输出 B,反之输出 A,并且输出一个数字 NumNum 表示你第一步选择 NumNum 将获得胜利。如果存在多个解,输出最小的那个。

原存档的输入/输出样例排版损坏,已移除。可核对:N=2时输出B;N=3时输出A 3。