====== Codeforces Round #641 (Div. 2) ======
===== A. Orac and Factors =====
大致题意:$f(n)$为n除1外的最小约数,令$g(n)=f(n)+n$,求$g_k(n)$
易证,$f(n)$与$n$同奇偶,所以$f(n)+n$必为偶数。又$f(2k)=2,k\in N$,所以我们只需先计算$f(n)+n$,然后加$k-1$个2即可。
代码:
#include
int main()
{
int t;
scanf("%d",&t);
for (int kkk=1;kkk<=t;kkk++)
{
int n,k;
scanf("%d%d",&n,&k);
if (n%2==0)
printf("%d\n",n+k*2);
else
{
int i;
for (i=2;i<=n;i++)
if (n%i==0)
break;
printf("%d\n",n+i+(k-1)*2);
}
}
}
===== B. Orac and Models =====
大致题意:给定一个序列$a_n$,求满足下面条件的递增子列$s_n$的最大长度:
1.$s_i\ mod \ s_{i-1}=0,\forall 1i且j\ mod\ i=0$
代码:
#include
#include
#include
using namespace std;
int dp[100001];
int a[100001];
int main()
{
int T;
scanf("%d",&T);
while (T--)
{
memset(dp,0,sizeof(dp));
int n;
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
dp[i]=1;
}
for (int i=1;i<=n;i++)
for (int j=2*i;j<=n;j+=i)
if (a[j]>a[i])
{
dp[j]=max(dp[j],dp[i]+1);
}
int ans=0;
for (int i=1;i<=n;i++)
ans=max(ans,dp[i]);
printf("%d\n",ans);
}
return 0;
}
===== C. Orac and LCM =====
大致题意:求$\gcd(\{lcm(\{a_i,a_j\})|i
#include
#include
#include
#include
using namespace std;
long long a[200001];
int pow(int a,int b)
{
int an=1;
for (int i=1;i<=b;i++)
an*=a;
return an;
}
int main()
{
srand(2);
int n;
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%lld",&a[i]);
if (n==2)
{
printf("%lld",a[1]*a[2]/__gcd(a[1],a[2]));
return 0;
}
long long an=0;
for (int i=2;i<=n;i++)
an=__gcd(an,(a[i]*a[i-1])/__gcd(a[i],a[i-1]));
int time=0;
vector fact;
int tmp=2;
while(an>=tmp)
{
if (an%tmp==0)
fact.push_back(tmp);
while(an%tmp==0)
an/=tmp;
tmp++;
}
int ans=1;
for (auto factor:fact)
{
vector sorts;
int min1=1e9,min2=1e9;
for (int i=1;i<=n;i++)
{
int now=0;
int p=a[i];
while (p%factor==0)
p/=factor,now++;
sorts.push_back(now);
}
sort(sorts.begin(),sorts.end(),[](int a,int b)
{
return a