A：暴力水题。
B：暴力水题。
A，B具体可参考我CF上的代码。

C：注意到只要两个串长度相等且各个数位的和相等，就可以互相转换，所以简单的dp预处理就能O1询问答案。
D：公式题，http://hi.baidu.com/wjbzbmr/blog/item/5aa2143735bc450391ef3953.html 有证明。

E：我们不妨直接暴力dp，考虑数位d，假设n在d下有len位，那么状态就是(d+1)^len (每位是？或者[0,d-1])，注意到d=2的时候。。状态数非常多，我昨天晚上的想法是固定前几位然后后面再dp，tourist的算法就是这个，我比较弱没写出来。。不过，注意到我们可以一次算很多个素数！比如我们可以计算余2*3*5*7*11的结果。。。。这样再暴力dp。。能卡过。。。