https://ac.nowcoder.com/acm/contest/923/B
我真是個辣雞,現在才知道線性篩,
思路:對于每個數字的階乘,開一個一維數組記錄每個數字出現的個數,先利用一維差分将每個數字的階乘中出現都得數字累加個數,然後再利用線性篩中,已知每個數字的最小質因數是什麼,在比較過程中,我們可以從大到小比較,如果發現對于同一個數字它的出現次數不同,我們可以把這個數字劃分為兩個數字的乘積形式(已知每個數字的最小質因數都是固定的),如果數字相同就不用管了,最後在周遊一遍看看是否每個位置的數字個數都相同就可以了。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int v[maxn],prime[maxn];
int a[maxn],b[maxn];
int da[maxn],db[maxn];
void primes(int n)
{
memset(v,0,sizeof(v));
int m=0;
for(int i=2; i<=n; i++)
{
if(v[i]==0)
{
v[i]=i;
prime[++m]=i;
}
for(int j=1; j<=m; j++)
{
if(prime[j]>v[i]||prime[j]>n/i) break;
v[i*prime[j]]=prime[j];
}
}
}
int main()
{
primes(100000);
int t;
scanf("%d",&t);
for(int it=1; it<=t; it++)
{
int n,m;
scanf("%d%d",&n,&m);
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(da,0,sizeof(da));
memset(db,0,sizeof(db));
for(int i=1; i<=n; i++)
{
int t;
scanf("%d",&t);
if(t>1)
{
da[2]++;
da[t+1]--;
}
}
for(int i=1; i<=m; i++)
{
int t;
scanf("%d",&t);
if(t>1)
{
db[2]++;
db[t+1]--;
}
}
for(int i=2; i<=1e5; i++)
{
da[i]+=da[i-1];
db[i]+=db[i-1];
a[i]+=da[i];
b[i]+=db[i];
}
for(int i=1e5; i>=2; i--)
{
if(a[i]!=b[i])
{
int zy1=i/v[i];
int zy2=i/zy1;
int ta=a[i];
int tb=b[i];
a[i]=b[i]=0;
a[zy1]+=ta;
a[zy2]+=ta;
b[zy1]+=tb;
b[zy2]+=tb;
}
}
int flag=1;
for(int i=2; i<=1e5; i++)
{
if(a[i]!=b[i])
{
// printf("%d %d\n",a[i],b[i]);
flag=0;
break;
}
}
if(flag)
printf("equal\n");
else
printf("unequal\n");
}
}
轉載于:https://www.cnblogs.com/dongdong25800/p/11067710.html