my solution of Atcoder Beginner Contest 293 E

Revision en10, by 1xx55, 2023-03-14 08:37:00

The goal is to find $$$\sum^{X-1}_{i=0}A^{i}$$$ $$$ mod $$$ $$$m$$$ , and a simple thought is that we can calculate $$$\frac{A^{X}-1}{A-1}$$$. But when we divide $$$A^{X}-1$$$ by $$$A-1$$$ then $$$mod$$$ $$$m$$$, problem occurs: when we calculate $$$A^{X}-1$$$ , it's already $$$mod$$$ $$$m$$$ ,and there's maybe no reverse to it.

To solve this problem , I use a simple method: store $$$A^i$$$ with two numbers : $$$k$$$ and $$$r$$$ ,satisfying

$$$A^i \equiv k(A-1)+r \pmod {m(A-1)}$$$ , $$$0 \leq r \le A-1$$$

When we calculate $$$A^{x}$$$,we refresh $$$k$$$ and $$$r$$$ by multiplication ,then refresh $$$k$$$ by modulo $$$m$$$ , and refresh $$$r$$$ when $$$r \ge A-1 $$$ : we do $$$k$$$ $$$+=$$$ $$$r/(A-1)$$$ and $$$r$$$ $$$=$$$ $$$r$$$ % $$$(A-1)$$$ ,like a carry.

We can prove that $$$r=0$$$ when $$$A=2$$$ and $$$r=1$$$ when $$$A=1$$$.if $$$A=1$$$ , we can NOT use $$$k$$$ and $$$r$$$ to store this num for $$$A-1=0$$$ . But this case is easy to solve . The result is obviously $$$X \bmod m$$$ .

Since we get

$$$A^X \equiv k_{X}(A-1)+r_X \pmod {m(A-1)}$$$

we can get

$$$\frac{A^X-1}{A-1} \equiv k_{X} \pmod{m} (A \geq 2)$$$

So the answer is $$$k_{X}$$$ . Noted that this method is free to change the denominator(in this problem it's $$$A-1$$$).

Code here (GNU C11)

#include<stdio.h>
#define yes printf("Yes\n")
#define no printf("No\n")
//WA but score 500 :)

struct num{
	// store number in form k*deno+r ( 0 <= r < deno)
	// to solve (number^b / deno) mod Mod = ?
	long long k;
	long long r;
};

struct num qtimes(struct num n,long long b,long long deno,long long mod){
	//Warning :deno != 0 
	 if(b>=2){
	 	long long tmpk = (((n.k*n.k%mod)*deno)%mod + (2*n.r*n.k) % mod + n.r*n.r/deno)%mod;
	 	long long tmpr = n.r*n.r % deno;
	 	if (b%2==0) return qtimes({tmpk,tmpr},b/2,deno,mod);
	 	else{
		  	struct num tmpn = qtimes({tmpk,tmpr},b/2,deno,mod);
			long long tk2 = (((n.k*tmpn.k)%mod*deno)%mod + (n.r*tmpn.k+n.k*tmpn.r) % mod + n.r*tmpn.r/deno)%mod;
			long long tr2 = n.r*tmpn.r % deno;
			return {tk2,tr2};  	
		}
	 }
	 else if(b==1) return {(n.k%mod+n.r/deno)%mod,n.r%deno};
	 else if(b==0) return {0,1};
}

int main(){
	long long a,x,m;
	scanf("%lld%lld%lld",&a,&x,&m);
	if (a==1) {
		printf("%lld",x%m); 
		return 0;	
	}
	struct num result = qtimes({1,1},x,a-1,m);
	printf("%lld",result.k+(result.r-1)/(a-1));
	// result = (A^x) ,--> {ans , 1}
}

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en14 English 1xx55 2023-03-14 10:10:25 0 (published)
en13 English 1xx55 2023-03-14 10:04:56 1205 (saved to drafts)
en12 English 1xx55 2023-03-14 08:46:09 0 (published)
en11 English 1xx55 2023-03-14 08:45:53 31 (saved to drafts)
en10 English 1xx55 2023-03-14 08:37:00 0 (published)
en9 English 1xx55 2023-03-14 08:35:02 4 Tiny change: ' , we can NOT use $k$ a' -> ' , we can **NOT** use $k$ a'
en8 English 1xx55 2023-03-14 08:33:58 13 Tiny change: 'nCode here:\n~~~~~\n#' -> 'nCode here (GNU C11)\n~~~~~\n#'
en7 English 1xx55 2023-03-14 08:29:50 1155 Tiny change: 'n\nCode:\n ' -> 'n\nCode:\n~~~~~\nincl\n~~~~~\n\n\n '
en6 English 1xx55 2023-03-14 08:16:01 135 Tiny change: '} \equiv \left\{k_{X} & ' -> '} \equiv \{k_{X} & '
en5 English 1xx55 2023-03-14 07:59:14 337 Tiny change: ' $r=$\left{ 01A=2A>20A=21A>2\begin{arr' -> ' $r=$\left\{ \begin{arr'
en4 English 1xx55 2023-03-14 06:39:52 4 Tiny change: ')+r \pmod m(A-1)$ , $0 \le' -> ')+r \pmod {m(A-1)}$ , $0 \le'
en3 English 1xx55 2023-03-14 06:38:22 80 Tiny change: ': we do $k% %+=% %r/(A-1)$ a' -> ': we do $k$ $+=$ $r/(A-1)$ a'
en2 English 1xx55 2023-03-14 06:16:49 524 Tiny change: '{i=0}A^{i} mod m$' -> '{i=0}A^{i}$ $ mod $ $m$'
en1 English 1xx55 2023-03-14 05:56:14 94 Initial revision (saved to drafts)