题目大意

传送门

本题目是看教程

思路

本文是看教程：O(n)可以解决的2道题

习题的第一题，是比较好的思路。

遇到数相关的题目，凡是提到了 K 以及 K?1 ，就往欧拉公式，费马小定理上想。

• 欧拉函数ph(n): 所有小于n且与n互质的数的个数
  比如说ph(12)=4,[1,5,7,11与12互质]

• 欧拉定理: aph(n)=1(modn)
  n和a是正整数并且互质的时候，欧拉定理成立。
  当欧拉公式中的n为质数的时候，显然 ph(p)=p?1 ，则可得：

• 费马小定理： a(p?1)=1(modp)

这题目中
Smod(p?1)
=(S[0]?Pn+S[1]?Pn?1+...+S[n?1]?P0)mod(p?1)
=(S[0]+S[1]+...+S[n?1])mod(p?1)

所以判断各个位数上加起来能否被p-1整除就好了，若能整除答案就是p。

代码

#include<stdio.h>
#include<string>
#include<iostream>
#include<cstring>
using namespace std;

#define max_int(a,b) (a>b)? a:b

char S[100005];

int char2int(char a){
    if('A'<=a && a<='Z') return a-'A'+10;
    else return a-'0';
}



int main ()
{
    scanf("%s",S);
    int len = strlen(S);
    int ans = 0;
    int max_b = 0;
    for(int i=0;i<len;i++){
        ans += char2int(S[i]);
        max_b = max_int(max_b,char2int(S[i]));
    }

    int flag = 0;
    for(int i=max_b+1;i<=36;i++)
    {
        if(ans%(i-1)==0) {printf("%dn",i);flag =1; break;}
    }
    if(flag == 0)
        printf("No Solutionn");

}

Hit

费马小定理！