NC202233. 牛牛喜欢看小姐姐
描述
输入描述
第一行四个整数.
第二行个整数,分别表示
输出描述
一个整数表示恰好被个小姐姐经过的点数.
示例1
输入:
3 6 4 1 2 3 6
输出:
3
C++ 解法, 执行用时: 126ms, 内存消耗: 8896K, 提交时间: 2021-09-20 17:06:42
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ui unsigned int
#define ull unsigned long long
#define ld long double
#define X first
#define Y second
#define pb push_back
#define vi vector<int>
#define vii vector<vi>
#define lb lower_bound
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,b,a) for(int i=(b);i>=(a);--i)
#define rep0(i,a,b) for(int i=(a);i<(b);++i)
#define fore(i,a) for(int i=0;i<a.size();++i)
#define gc() getchar()
#define ls x<<1,l,m
#define rs x<<1|1,m+1,r
inline ll rd()
{
ll x=0,w=1;char c=gc();while(!isdigit(c)&&c!='-')c=gc();
if(c=='-')c=gc(),w=-1;while(isdigit(c))x=x*10+c-48,c=gc();return x*w;
}
const int N=110005,pr[]={2,3,5,7,11,13,31};
int n,s,tt,cc,pn[70],f[N];ll m,k,a[N],d[N],fp[70],fc[70];map<ll,int>mp,id;
inline ll mul(ll a,ll b,ll p){return (a*b-(ll)((ld)a*b/(ld)p)*p+p)%p;}
inline ll pw(ll a,ll b,ll p){ll r=1;a%=p;for(;b;b>>=1,a=mul(a,a,p))if(b&1)r=mul(r,a,p);return r;}
inline bool miller_rabin(ll n)
{
rep(i,0,6)if(n==pr[i])return 1;
ll r=n-1;int k=0;while(~r&1)r>>=1,k++;
rep(i,0,6)
{
ll x=pw(pr[i],r,n),y;
rep(i,1,k)
{
y=mul(x,x,n);
if(y==1&&x!=1&&x!=n-1)return 0;
x=y;
}
if(y!=1)return 0;
}
return 1;
}
#define Func(x) mul(x,x,n)+1
inline int rnd(){return rand()<<15^rand();}
inline ll div(ll n)
{
ll x=rand()%n+1,y=Func(x),k=1;int T=0;
while(x!=y)
{
ll t=k;k=mul(k,abs(y-x),n);
if(!k){t=__gcd(t,n);if(t>1)return t;break;}
if(T==100){T=0;ll t=__gcd(k,n);if(t>1)return t;}
x=Func(x);y=Func(Func(y));T++;
}
ll t=__gcd(k,n);return t>1?t:-1;
}
void pollard_rho(ll n)
{
while(~n&1){mp[2]++;n>>=1;}if(n==1)return;
if(miller_rabin(n)){mp[n]++;return;}
ll x;do x=div(n);while(x==-1);
pollard_rho(x);pollard_rho(n/x);
}
void dfs(int x,ll s,int o)
{
if(x==tt+1){d[o]=s;id[s]=o;return;}
ll t=1;rep(i,0,fc[x])dfs(x+1,s*t,o+i*pn[x]),t*=fp[x];
}
int main()
{
srand(time(0));n=rd();m=rd();k=rd();s=rd();
rep(i,1,n)a[i]=rd(),a[i]=__gcd(a[i],m);pollard_rho(m);
for(map<ll,int>::iterator it=mp.begin();it!=mp.end();it++){fp[++tt]=it->X;fc[tt]=it->Y;}
pn[0]=pn[1]=1;rep(i,2,tt)pn[i]=pn[i-1]*(fc[i-1]+1);
cc=pn[tt]*(fc[tt]+1);dfs(1,1,0);
rep(i,1,n)f[id[a[i]]]++;
rep(j,1,tt)
{
rep0(i,0,cc)
{
int t=i/pn[j]%(fc[j]+1);
if(t)f[i]+=f[i-pn[j]];
}
}
rep0(i,0,cc)f[i]=f[i]==s;
rep(j,1,tt)
{
per(i,cc-1,0)
{
int t=i/pn[j]%(fc[j]+1);
if(t)f[i]-=f[i-pn[j]];
}
}
ll ans=n==s;
rep0(i,0,cc)ans+=f[i]*(k/d[i]);
printf("%lld\n",ans);return 0;
}
C++14(g++5.4) 解法, 执行用时: 197ms, 内存消耗: 10660K, 提交时间: 2020-02-29 01:44:34
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace PollardRho{
map<ll,int> facs;
inline ll mulmod(ll x,ll y,ll z){
return (x*y-(ll)((x*(long double)y+0.5)/z)*z+z)%z;
}
inline ll powmod(ll x,ll y,ll z){
ll s=1;for(;y;y>>=1,x=mulmod(x,x,z))if(y&1)s=mulmod(s,x,z);
return s;
}
bool isPrime(ll p){
const int n=9,a[n]={2,3,5,7,11,13,17,19,23};
if(p==2)return true;
if(p==1||!(p&1))return false;
ll D=p-1; while(!(D&1))D>>=1;
for(int i=0;i<n&&a[i]<p;++i){
ll d=D,t=powmod(a[i],d,p);if(t==1)continue;
for(;d!=p-1&&t!=p-1;d<<=1)t=mulmod(t,t,p);
if(d==p-1)return false;
}
return true;
}
void getFactor(ll n){
if(n==1)return;
if(isPrime(n)){++facs[n];return;}
while(1){
ll c=rand()%n,i=1,x=rand()%n,y=x,k=2;
do{
ll d=__gcd(n+y-x,n);
if(d!=1&&d!=n){getFactor(d);getFactor(n/d);return;}
if(++i==k)y=x,k<<=1;
x=(mulmod(x,x,n)+c)%n;
}while(y!=x);
}
}
}
using namespace PollardRho;
const int N=110005;
int n,s,i,j,c[70],f[N],g[70];
ll m,k,a[N],tot,p[70],cnt,d[N],ans;
map<ll,int> id;
void sk(int k,ll now){
if(k==tot+1){d[++cnt]=now;id[now]=cnt;return;}
for(int i=0;i<=c[k];++i){sk(k+1,now);now*=p[k];}
}
int main(){
srand(time(0));
scanf("%d%lld%lld%d",&n,&m,&k,&s);
for(i=1;i<=n;++i)scanf("%lld",a+i),a[i]=__gcd(a[i],m);
getFactor(m);
for(auto t:facs){p[++tot]=t.first;c[tot]=t.second;}
for(g[i=tot]=1;i;--i)g[i-1]=g[i]*(1+c[i]);
sk(1,1);
for(i=1;i<=n;++i)++f[id[a[i]]];
for(j=1;j<=tot;++j)
for(i=1;i<=cnt;++i)if(d[i]%p[j]==0)f[i]+=f[i-g[j]];
for(i=1;i<=cnt;++i)f[i]=f[i]==s;
for(j=1;j<=tot;++j)
for(i=cnt;i;--i)if(d[i]%p[j]==0)f[i]-=f[i-g[j]];
for(i=1,ans=n==s;i<=cnt;++i)ans+=k/d[i]*f[i];
printf("%lld",ans);
}