Background

The eternal God OneInDark A linear algebra problem that no one can do , Beat with this question EI Master queen , Run to crashed Fight in front of the door .

But I didn't think ,crashed When the door is not fully opened , This problem was broken by him , This is beyond OneInDark The expectation of his second cut .

“ Just find me some linear algebra problems , Is this looking down on me ！” crashed Roaring . Voice is not falling. , The two gods appeared on the Simen arena .

“ Look good. , I'll give you a function problem this time ！……”

OneInDark Studied for a second , Something's wrong ,“ Um. ？ This is not a Tao generating function ！”

“ It's been a second for you ！ ha-ha ！ Be hurt ！” crashed laugh .

however OneInDark Immediately cut the problem faster than the speed of light , Make the final completion time become $-1\mathrm{ms}$ .

Topic

Defined function $F(x)={\prod }_{k=0}^{\lfloor \sqrt{x-1}\rfloor }(x-k^2)$ , Seek for $[l,r]$ How many positive integers are there in $x$ Satisfy $F(x)$ yes $m$ Multiple .

The input line l r m , Output a line of answers .

Limit ：$1\le l\le r\le 10^{12},2\le m\le 10^6$ ,1 s,128 mb .

Examples

1 1000000000000 1000000

599999999844

Answer key

When you think about this problem completely with your brain doing mathematical problem deduction , You lose. .

We might as well revise it to $F(x)={\prod }_{k=0}^{\lfloor \sqrt{x-1}\rfloor }((x-k^2)\mathrm{mod}m)$ , So it is not difficult to find ,$F(x+m)$ It must be $F(x)$ Multiple .

That means , modulus $m$ An equal series $x$ , stay $F(x)$ Whether it is $m$ The multiple of is monotonous .

therefore , We can find the smallest of every congruence class $x$ Satisfy $F(x)$ yes $m$ Multiple . Because of another $k^2$ All numerical contributions to a congruence class are equal , So we just need to find out $k^2$ Less than it should be $x$ One of the biggest $k$ That's it .

We enumerate from small to large $k$ , And statistics $k$ The contribution of . But such violence will be overtime .

We might as well $m$ Prime factor decomposition ,$m=\prod p_i^{w_i}$, For each $p_i$ Consider enumeration alone $k$ It's a contribution , Find out that each congruence class contains $p_i^{w_i}$ Minimum timestamp of , Finally, find the maximum value of the timestamp for each congruence class .

So every enumeration $k$ When , from $k^2\mathrm{mod}m$ Start dancing , Every time you jump back $p_i$ length , Maintain and $O(1)$ Skip all already included $p_i^{w_i}$ The location of , Violence multiplies contribution . Because every calculation will make a congruence $p_i$ More times , Finally arrive at $p_i^{w_i}$ stop it , It can be proved that the time complexity is $O(m\log m)$ Of .

Total algorithm time complexity $O(m\log m+\sqrt{r}\log m)$ .

CODE

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<random>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#pragma GCC optimize(2)
using namespace std;
#define MAXN 1000005
#define LL long long
#define ULL unsigned long long
#define ENDL putchar('\n')
#define DB double
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second
#define PR pair<int,int>
#define UIN unsigned int
int xchar() {
    
	static const int maxn = 1000000;
	static char b[maxn];
	static int pos = 0,len = 0;
	if(pos == len) pos = 0,len = fread(b,1,maxn,stdin);
	if(pos == len) return -1;
	return b[pos ++];
}
// #define getchar() xchar()
inline LL read() {
    
	LL f = 1,x = 0;int s = getchar();
	while(s < '0' || s > '9') {
    if(s<0)return -1;if(s=='-')f=-f;s = getchar();}
	while(s >= '0' && s <= '9') {
    x = (x<<1) + (x<<3) + (s^48);s = getchar();}
	return f*x;
}
void putpos(LL x) {
    if(!x)return ;putpos(x/10);putchar((x%10)^48);}
inline void putnum(LL x) {
    
	if(!x) {
    putchar('0');return ;}
	if(x<0) putchar('-'),x = -x;
	return putpos(x);
}
inline void AIput(LL x,int c) {
    putnum(x);putchar(c);}

int MOD = 1;
int n,m,s,o,k;
int dp[MAXN],f[MAXN];
LL c[MAXN];
PR fct[MAXN];
int hd[MAXN],nx[MAXN];
int main() {
    
	LL l = read(),r = read();MOD = read();
	int nn = MOD;
	for(int i = 2;i*i <= nn;i ++) {
    
		if(nn % i == 0) {
    
			int ct = 0;
			while(nn % i == 0) nn /= i,ct ++;
			fct[++ m] = {
    i,ct};
		}
	}
	if(nn > 1) fct[++ m] = {
    nn,1};
	for(int i = 1;i <= m;i ++) {
    
		int x = fct[i].FI,w = fct[i].SE,xx = 1;
		for(int j = 0;j < w;j ++) xx *= x;
		for(int j = 0;j < x;j ++) hd[j] = -1;
		for(int j = 0;j < MOD;j ++) {
    
			f[j] = 1000001,c[j] = 1;
			nx[j] = hd[j%x]; hd[j%x] = j;
		}
		for(int j = 0;j*1ll*j < r;j ++) {
    
			int ad = j*1ll*j%x,po = j*1ll*j%MOD;
			vector<int> emp;
			int tl = hd[ad]; hd[ad] = -1;
			for(int y = tl;y>=0;y = tl) {
    
				tl = nx[y];
				int le = (y+MOD-po)%MOD;
				(c[y] *= le) %= MOD;
				if(c[y] % xx == 0) f[y] = j;
				else nx[y] = hd[ad],hd[ad] = y;
			}
		}
		for(int j = 0;j < MOD;j ++) {
    
			dp[j] = max(dp[j],f[j]);
		}
	}
	LL ans = 0;
	for(int i = 0;i < MOD;i ++) {
    
		LL st = dp[i]*1ll*dp[i]+1;
		st = st + (MOD-st%MOD+i)%MOD;
		if(st <= r) ans += (r-st)/MOD+1;
		if(st < l) ans -= (l-1-st)/MOD+1;
	}
	AIput(ans,'\n');
	return 0;
}