当前位置:网站首页>(lightoj - 1370) Bi shoe and phi shoe (Euler function tabulation)
(lightoj - 1370) Bi shoe and phi shoe (Euler function tabulation)
2022-07-06 16:23:00 【AC__ dream】
Topic link :Bi-shoe and Phi-shoe - LightOJ 1370 - Virtual Judge
give n A sequence of numbers a[], For each number ai Find an Euler function whose value is greater than or equal to ai Number of numbers bi, Find all the numbers found bi The sum of the minimum values of sum( Euler function is specified here 1 The value of is 0)
Input
Yes T(T<=100) Group data , Each set of data has two lines , The first line gives n(n<=10000) The second line gives the length n Sequence a[],ai The value range of is [1,1000000]
Output
Output a number sum
Sample Input
3
5
1 2 3 4 5
6
10 11 12 13 14 15
2
1 1
Sample Output
Case 1: 22 Xukha
Case 2: 88 Xukha
Case 3: 4 Xukha
analysis : This problem is to examine the Euler function and make a table , If you don't know this, you can check my previous blog , It introduces in detail the principle of Euler function table , Here is the blog address : Euler function method and its basic application _AC__dream The blog of -CSDN Blog _ Euler function method
When we find the Euler function of all numbers , We can directly check the table , Here we can use a greedy thought , First of all, we can know from the definition of Euler function , The Euler function value is greater than x The number of must be greater than x, So every time we look up the first Euler function, the value is greater than a[i] The number of hours can be from a[i] Start looking up the table , Before checking the table, we can check a Array to sort , This will play an optimization role to a certain extent , Then check the table in an increasing order , Here is the code :
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
const int N=1000005;// There must be an Euler function greater than 1000000 Number of numbers , Including prime numbers 1000003 that will do
bool vis[N];
int prime[N],o[N],cnt,a[N];
void init()
{
o[1]=0;// Default in this question 1 The Euler function of is 0
for(int i=2;i<N;i++)
{
if(!vis[i])
{
prime[++cnt]=i;
o[i]=i-1;
}
for(int j=1;j<=cnt&&i*prime[j]<N;j++)
{
vis[i*prime[j]]=true;
if(i%prime[j]==0)
{
o[i*prime[j]]=o[i]*prime[j];
break;
}
else
o[i*prime[j]]=o[i]*(prime[j]-1);
}
}
}
int main()
{
init();
int T;
cin>>T;
for(int _=1;_<=T;_++)
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+n+1);
int pos=a[1];
long long ans=0;
for(int i=1;i<=n;i++)
{
while(o[pos]<a[i]) pos++;
ans+=pos;
}
printf("Case %d: %lld Xukha\n",_,ans);
}
return 0;
}
边栏推荐
- 力扣:第81场双周赛
- Interval sum ----- discretization
- Some problems encountered in installing pytorch in windows11 CONDA
- Opencv learning log 26 -- detect circular holes and mark them
- Penetration test (4) -- detailed explanation of meterpreter command
- Codeforces Round #801 (Div. 2)A~C
- QT implementation window gradually disappears qpropertyanimation+ progress bar
- Opencv learning log 27 -- chip positioning
- QT style settings of qcobobox controls (rounded corners, drop-down boxes, up expansion, editable, internal layout, etc.)
- Flag framework configures loguru logstore
猜你喜欢
力扣——第298场周赛
Codeforces Round #801 (Div. 2)A~C
力扣:第81场双周赛
antd upload beforeUpload中禁止触发onchange
Problem - 922D、Robot Vacuum Cleaner - Codeforces
QT implementation fillet window
D - function (HDU - 6546) girls' competition
1013. Divide the array into three parts equal to and
C language must memorize code Encyclopedia
Problem - 922D、Robot Vacuum Cleaner - Codeforces
随机推荐
OneForAll安装使用
浏览器打印边距,默认/无边距,占满1页A4
Differential (one-dimensional, two-dimensional, three-dimensional) Blue Bridge Cup three body attack
Shell Scripting
Specify the format time, and fill in zero before the month and days
Some problems encountered in installing pytorch in windows11 CONDA
Classic application of stack -- bracket matching problem
Openwrt build Hello ipk
QT实现圆角窗口
快速转 TypeScript 指南
Problem - 922D、Robot Vacuum Cleaner - Codeforces
Find 3-friendly Integers
Suffix expression (greed + thinking)
Sanic异步框架真的这么强吗?实践中找真理
Vs2019 initial use
Frida hook so layer, protobuf data analysis
Sword finger offer II 019 Delete at most one character to get a palindrome
Interval sum ----- discretization
“鬼鬼祟祟的”新小行星将在本周安全掠过地球:如何观看
Codeforces Round #802(Div. 2)A~D