{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"Given a prime P, 2 \u0026lt;\u003d P \u0026lt; 2\u003csup\u003e31\u003c/sup\u003e, an integer B, 2 \u0026lt;\u003d B \u0026lt; P, and an integer N, 1 \u0026lt;\u003d N \u0026lt; P, compute the discrete logarithm of N, base B, modulo P. That is, find an integer L such that \r\u003cbr\u003e\u003cpre\u003e B\u003csup\u003eL\u003c/sup\u003e \u003d\u003d N (mod P)\u003c/pre\u003e"}},{"title":"Input","value":{"format":"HTML","content":"Read several lines of input, each containing P,B,N separated by a space."}},{"title":"Output","value":{"format":"HTML","content":"For each line print the logarithm on a separate line. If there are several, print the smallest; if there is none, print \"no solution\". "}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 2 1\r\n5 2 2\r\n5 2 3\r\n5 2 4\r\n5 3 1\r\n5 3 2\r\n5 3 3\r\n5 3 4\r\n5 4 1\r\n5 4 2\r\n5 4 3\r\n5 4 4\r\n12345701 2 1111111\r\n1111111121 65537 1111111111\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\r\n1\r\n3\r\n2\r\n0\r\n3\r\n1\r\n2\r\n0\r\nno solution\r\nno solution\r\n1\r\n9584351\r\n462803587\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"The solution to this problem requires a well known result in number theory that is probably expected of you for Putnam but not ACM competitions. It is Fermat\u0027s theorem that states \r\u003cbr\u003e\u003cpre\u003e B\u003csup\u003e(P-1)\u003c/sup\u003e \u003d\u003d 1 (mod P)\u003c/pre\u003e\r\u003cbr\u003efor any prime P and some other (fairly rare) numbers known as base-B pseudoprimes. A rarer subset of the base-B pseudoprimes, known as Carmichael numbers, are pseudoprimes for every base between 2 and P-1. A corollary to Fermat\u0027s theorem is that for any m \r\u003cbr\u003e\u003cpre\u003e B\u003csup\u003e(-m)\u003c/sup\u003e \u003d\u003d B\u003csup\u003e(P-1-m)\u003c/sup\u003e (mod P) .\u003c/pre\u003e"}}]}