jzoj 2554. 【NOIP2011模拟9.7】帕秋莉·诺蕾姬

发布于 2019-03-28  7 次阅读


题目描述

 在幻想乡,帕秋莉·诺蕾姬是以宅在图书馆闻名的魔法使。这一天帕秋莉又在考虑如何加强魔法咒语的威力。帕秋莉的魔法咒语是一个仅有大写字母组成的字符串,我们考虑从’A’到’Z’分别表示0到25的数字,于是这个魔法咒语就可以看作一个26进制数。帕秋莉通过研究发现,如果一个魔法咒语所代表的数能够整除10进制数M的话,就能够发挥最大的威力。若当前的魔法咒语并不能整除M,帕秋莉只会将其中两个字符的位置交换,尽量让它能够被M整除,当然由于某些咒语比较特殊,无论怎么改变都不能达到这个目的。请你计算出她能否只交换两个字符就让当前咒语被M整除。(首位的’A’为前导0)

输入

 第1行:1个字符串,长度不超过L。
  第2行:1个正整数,M

输出

第1行:用空格隔开的2个整数,输出时先输位置靠前的那个。
  如果存在多种交换方法,输出字典序最小的,比如1 3和1 5都可以达到目的,就输出1 3;1 3和2 4都行时也输出1 3。注意字符串下标从左到右依次为1到L开始。如果初始魔法咒语已经能够整除M,输出”0 0”;若无论如何也不能到达目的输出”-1 -1”。

思路

先把26的倍数全部求出来将26进制转换为10进制,然后根据同余原理,可以每一次都mod m来保证不会炸,在进行此操作时将全部的余数加起来如果最后是等于0就直接输出‘0 0’,然后后面枚举没两个字母的26进制数,将他们相减后化成10进制数,这个数加上上面我们求出的数 mod m 如果等于0就直接输出当前的i和j

var
  f,xx:array[0..10000] of longint;
  st:ansistring;
  i,j,k,n,m,s,x,y,le,t:longint;
begin
  readln(st);
  readln(m);

  le:=length(st);
    xx[le]:=1;

  for i:=le-1 downto 1 do
    xx[i]:=(26*xx[i+1]) mod m;

  for i:=le downto 1 do
    begin
      f[le-i+1]:=ord(st[le-i+1])-65;
      t:=(t+f[le-i+1]*xx[le-i+1]) mod m;
    end;

  if t=0 then
    begin
      writeln(0,' ',0);
      halt;
    end;

  for i:=1 to le do
    for j:=1 to le do
      begin
        x:=((f[j]-f[i])*xx[i]+(f[i]-f[j])*xx[j]) mod m;
        if (x+t) mod m=0 then
          begin
            writeln(i,' ',j);
            halt;
          end;
      end;
  writeln(-1,' ',-1);
end.
]]>