zwu_2020015020

152

edgdcgxgbx

guankunkun

OneMorePuzzle

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e6+5;

int primes[N],cnt;
int phi[N];
bool st[N];

void get_eulers(int n)
{
phi[1]=1;
for(int i=2;i<=n;i++){
if(!st[i]){
primes[cnt++]=i;
phi[i]=i-1;
}
for(int j=0;primes[j]<= n/i;j++){
st[primes[j]*i]=true;
if(i%primes[j]==0){
phi[primes[j]*i] = phi[i]* primes[j];
break;
}
phi[primes[j] * i] = phi[i] * (primes[j] - 1);
}
}
}

int main()
{
int n;
cin>>n;
get_eulers(n);
long long sum=0;
for (int i = 1; i <= n; i ++ ) sum+=phi[i];
cout << sum<<endl;
return 0;
}



#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
int t;
cin>>t;
while(t--){
int a;
cin>>a;
int res=a;
for (int i = 2; i <= a/i; i ++ ){
if(a%i==0){
res = res/i*(i - 1);
while(a%i==0) a/=i;
}
}
if(a>1) res=res/a*(a-1);
cout<<res<<endl;
}
return 0;
}


#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
int t;
cin>>t;
while(t--){
int a;
cin>>a;
int res=a;
for (int i = 2; i <= a/i; i ++ ){
if(a%i==0){
res = res/i*(i - 1);
while(a%i==0) a/=i;
}
}
if(a>1) res=res/a*(a-1);
cout<<res<<endl;
}
return 0;
}


#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int gcd(int a,int b){
if(a%b==0) return b;
return gcd(b,a%b);
}

int main()
{
int n;
cin>>n;
while (n -- ){
int a,b;
cin>>a>>b;
cout<<gcd(a,b)<<endl;
}
}


#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

vector<int>d,t;

int main()
{
int n;
cin>>n;
char c;
int x;
while(n--){
cin>>c>>x;
if(c=='T') t.push_back(x);
else d.push_back(x);
}
sort(t.begin(),t.end());
sort(d.begin(),d.end());
int v=1;
int i=0,j=0;
double T=0,len=0;
while(i<d.size()&&j<t.size()){
double t1 =  t[j] - T;
double t2 = (d[i] - len)*v;
if(t1==t2){
T = t[j];
len = d[i];
v += 2;
i++;
j++;
}
else if(t1 < t2){//先到达减速时间
len += (t[j] - T) / v;
T = t[j];
v++, j++;
}
else{//先到达减速位置
T += (d[i] - len) * v;
len = d[i];
v++, i++;
}
}
while(i<d.size()){
T += (d[i] - len) * v;
len = d[i];
v++, i++;
}
while(j<t.size()){
len += (t[j] - T) / v;
T = t[j];
v++, j++;
}
cout<<(int)(T + (1000 - len) * v + 0.500001)<<endl;
return 0;
}


#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;

const int N = 1e5+5;
int a[N];
map<int,int>b;

int main()
{
int n;
cin>>n;
for (int i = 1; i <= n; i ++ ){
cin>>a[i];
if(a[i]>a[i-1]){
b[a[i-1]]++,b[a[i]]--;
}
}
int ans=0,sum=0;
for(auto &[x,v]:b){
sum+=v;
ans=max(sum,ans);
}
cout<<ans<<endl;
return 0;
}


#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;

typedef long long LL;
const int mod =  1e9+7;

unordered_map<int,int> mp;

int main()
{
int n;
cin>>n;
int x;
while (n -- ){
cin>>x;
for(int i=2;i<=x/i;i++){
while(x%i==0){
x/=i;
mp[i]++;
}
}
if(x>1) mp[x]++;
}
LL ans=1;
for(auto &[x,v]:mp){
LL t=1;
while(v--) t=(t*x+1)%mod;
ans=ans*t%mod;
}
cout<<ans<<endl;
}


#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;

typedef long long LL;
const int mod =  1e9+7;

unordered_map<int,int> mp;

int main()
{
int n;
cin>>n;
int x;
while (n -- ){
cin>>x;
for(int i=2;i<=x/i;i++){
while(x%i==0){
x/=i;
mp[i]++;
}
}
if(x>1) mp[x]++;
}
LL ans=1;
for(auto &[x,v]:mp){
ans=ans*(v+1)%mod;
}
cout<<ans<<endl;
}


#include<bits/stdc++.h>
using namespace std;
const int N= 10;
char s[N][N];
int n;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
bool st[N][N];
int ans=0;
void dfs(int x,int y,int l,int r)
{

if(l>0&&l==r)
{
ans=max(ans,l+r);
return ;
}
for(int i=0;i<4;i++)
{
int xx=x+dx[i],yy=y+dy[i];
if(xx<1||yy<1||xx>n||yy>n||st[xx][yy])continue;

if(r>0&&s[xx][yy]=='(')
{
continue;
}

st[xx][yy]=true;

if(s[xx][yy]=='(')dfs(xx,yy,l+1,r);
else dfs(xx,yy,l,r+1);

st[xx][yy]=false;//回溯

}

return ;

}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%s",s[i]+1);
}
if(s[1][1]==')')
{
puts("0");
return 0;
}
st[1][1]=true;
dfs(1,1,1,0);
cout<<ans<<endl;
return 0;
}


### 算法1

O(n^2*logn)

#### C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e3+5;

int a[N];

int main()
{
int n;
cin>>n;
int ans=0;
for (int i = 0; i < n; i ++ ) cin>>a[i];
sort(a,a+n);
int l,r; //l=左边界 r=右边界
for (int i = 0; i < n-2; i ++ ){
for (int j = i+1; j < n-1; j ++ ){
l=lower_bound(a,a+n,a[j]+a[j]-a[i])-a; //lower 找大于等于该数 输出地址 所以-a 就输出下标
r=upper_bound(a,a+n,a[j]+2*(a[j]-a[i]))-a; //upper 找大于该数 输出地址 如果用lower找那还要判断这个点是不是在右边界
ans+=r-l; //简化前:r-1 此时才是我们需要的下标 r-1-l+1 加上减去l 此时多减了一个l点 所以是r-l
}
}
cout<<ans<<endl;
}