为什么一个能过,另一个TLE
  • 板块CF594D REQ
  • 楼主zyn0309
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/6/17 15:08
  • 上次更新2025/6/18 15:08:22
查看原帖
为什么一个能过,另一个TLE
864310
zyn0309楼主2025/6/17 15:08

TLE on#30

#include<bits/stdc++.h>
#include<bits/extc++.h>
namespace fast_IO {
#define IOSIZE 1000000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
using namespace __gnu_pbds;
const int N=2e5+10,mod=1e9+7;
int n,m,a[N],prime[N],cnt,inv[N*5],res=1,ans[N],siz[N*5],inv2[N*5],bl[N],siz2[169][N],ma[N*5];
bool is[5*N],use[5*N];
struct query{
	int l,r,id;
}q[N];
#define pii  pair<int,int> 
#define mk(a,b) {a,b}
#define pb push_back
vector<int>p[10*N];
inline int qpow(int a,int b){
	int res=1;
	while(b){
	  if(b&1)res=1ll*res*a%mod;
	  a=1ll*a*a%mod;
	  b>>=1;
	}
	return res;
}
inline void euler(){
	is[1]=1;
	for(int i=2;i<=1e6;++i){
	  if(!is[i])prime[++cnt]=i;
	  for(int j=1;j<=cnt&&i*prime[j]<=1e6;++j){
	  	is[i*prime[j]]=1;
	  	if(!(i%prime[j]))break;
	  }
	}
	for(int i=1;i<=cnt;++i){
	  for(int x=1;x*prime[i]<=1e6;++x){
		int val=x*prime[i];
		if(!use[val])continue;
		ma[val]=prime[i];
		while(!(val%prime[i]))p[x*prime[i]].pb(i),val/=prime[i];
	  }
	}
}
inline bool cmp(query a,query b){
	if(bl[a.l]!=bl[b.l])return a.l<b.l;
	else return (bl[a.l]&1)?a.r<b.r:a.r>b.r;
}
inline void add(int val){
	int x=ma[val];
	if(x>1000){
	  ++siz[x];
	  if(siz[x]==1)res=1ll*res*(x-1)%mod;
	  else res=1ll*res*x%mod;
	}
}
inline void del(int val){
	int x=ma[val];
	if(x>1000){
	  --siz[x];
	  if(!siz[x]){
	  	if(!inv2[x])inv2[x]=qpow(x-1,mod-2);
	    res=1ll*res*inv2[x]%mod;
	  }
	  else{
	  	if(!inv[x])inv[x]=qpow(x,mod-2);
	    res=1ll*res*inv[x]%mod;
	  }
	}
}
cc_hash_table<int,int>mp[200];
signed main(){
	cin>>n;
	int len=1250;
	for(int i=1;i<=n;++i)cin>>a[i],bl[i]=(i/len)+1,use[a[i]]=1;
	euler();
	for(int i=1;i<=n;++i){
	  for(int j=1;prime[j]<1000;++j)siz2[j][i]=siz2[j][i-1];
	  for(auto x:p[a[i]]){
	  	if(prime[x]>1000)continue;
	  	++siz2[x][i];
	  }
	}
	cin>>m;
	for(int i=1;i<=m;++i){
	  cin>>q[i].l>>q[i].r;
	  q[i].id=i;
	}
	sort(q+1,q+1+m,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;++i){
	  while(r<q[i].r)add(a[++r]);
	  while(l>q[i].l)add(a[--l]);
	  while(r>q[i].r)del(a[r--]);
	  while(l<q[i].l)del(a[l++]);
	  int res2=1;
	  for(int j=1;prime[j]<1000;++j){
	  	int x=siz2[j][r]-siz2[j][l-1];
	  	if(!x)continue;
		if(mp[j].find(x-1)==mp[j].end())mp[j][x-1]=qpow(prime[j],x-1);
	  	res2=1ll*res2*(prime[j]-1)%mod*mp[j][x-1]%mod;
	  }
	  ans[q[i].id]=1ll*res*res2%mod;
	}
	for(int i=1;i<=m;++i)cout<<ans[i]<<"\n";
	return 0;
}

AC

#include<bits/stdc++.h>
#include<bits/extc++.h>
namespace fast_IO {
#define IOSIZE 1000000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
using namespace __gnu_pbds;
const int N=2e5+10,mod=1e9+7;
int n,m,a[N],prime[N],cnt,inv[N*5],res=1,ans[N],siz[N*5],inv2[N*5],bl[N],siz2[169][N],ma[N*5];
bool is[5*N],use[5*N];
struct query{
	int l,r,id;
}q[N];
#define pii  pair<int,int> 
#define mk(a,b) {a,b}
#define pb push_back
vector<int>p[10*N];
inline int qpow(int a,int b){
	int res=1;
	while(b){
	  if(b&1)res=1ll*res*a%mod;
	  a=1ll*a*a%mod;
	  b>>=1;
	}
	return res;
}
inline void euler(){
	is[1]=1;
	for(int i=2;i<=1e6;++i){
	  if(!is[i])prime[++cnt]=i;
	  for(int j=1;j<=cnt&&i*prime[j]<=1e6;++j){
	  	is[i*prime[j]]=1;
	  	if(!(i%prime[j]))break;
	  }
	}
	for(int i=1;i<=cnt;++i){
	  for(int x=1;x*prime[i]<=1e6;++x){
		int val=x*prime[i];
		if(!use[val])continue;
		ma[val]=prime[i];
		while(!(val%prime[i]))p[x*prime[i]].pb(i),val/=prime[i];
	  }
	}
}
inline bool cmp(query a,query b){
	if(bl[a.l]!=bl[b.l])return a.l<b.l;
	else return (bl[a.l]&1)?a.r<b.r:a.r>b.r;
}
inline void add(int val){
	int x=ma[val];
	if(x>1000){
	  ++siz[x];
	  if(siz[x]==1)res=1ll*res*(x-1)%mod;
	  else res=1ll*res*x%mod;
	}
}
inline void del(int val){
	int x=ma[val];
	if(x>1000){
	  --siz[x];
	  if(!siz[x]){
	  	if(!inv2[x])inv2[x]=qpow(x-1,mod-2);
	    res=1ll*res*inv2[x]%mod;
	  }
	  else{
	  	if(!inv[x])inv[x]=qpow(x,mod-2);
	    res=1ll*res*inv[x]%mod;
	  }
	}
}
cc_hash_table<int,int>mp[200];
signed main(){
	cin>>n;
	int len=1250;
	for(int i=1;i<=n;++i)cin>>a[i],bl[i]=(i/len)+1,use[a[i]]=1;
	euler();
	for(int i=1;i<=n;++i){
	  for(int j=1;prime[j]<1000;++j)siz2[j][i]=siz2[j][i-1];
	  for(auto x:p[a[i]]){
	  	if(prime[x]>1000)continue;
	  	++siz2[x][i];
	  }
	}
	cin>>m;
	for(int i=1;i<=m;++i){
	  cin>>q[i].l>>q[i].r;
	  q[i].id=i;
	}
	sort(q+1,q+1+m,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;++i){
	  while(r<q[i].r)add(a[++r]);
	  while(l>q[i].l)add(a[--l]);
	  while(r>q[i].r)del(a[r--]);
	  while(l<q[i].l)del(a[l++]);
	  ans[q[i].id]=res;
	}
	for(int i=1;i<=m;++i){
	  int res2=1;
	  for(int j=1;prime[j]<1000;++j){
	  	int x=siz2[j][q[i].r]-siz2[j][q[i].l-1];
	  	if(!x)continue;
		if(mp[j].find(x-1)==mp[j].end())mp[j][x-1]=qpow(prime[j],x-1);
	  	res2=1ll*res2*(prime[j]-1)%mod*mp[j][x-1]%mod;
	  }
	  ans[q[i].id]=1ll*ans[q[i].id]*res2%mod;
	}
	for(int i=1;i<=m;++i)cout<<ans[i]<<"\n";
	return 0;
}

两份代码唯一区别就是中间莫队那里的循环拆开了,下面那个AC的最大的点2600ms。

2025/6/17 15:08
加载中...