20小时前
/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
unordered_map<int,int>hash;
int pseudoPalindromicPaths (TreeNode* root) {

hash[root->val]++;
if(!root->left && !root->right)
{
int t = 0;
for(auto e:hash)
if(e.second%2)
t++;

hash[root->val]--;//(恢复叶子节点的现场)
return t<=1;
}

int res =0;
if(root->left)res += pseudoPalindromicPaths (root->left);
if(root->right)res += pseudoPalindromicPaths (root->right);

hash[root->val]--;//(恢复非叶子节点的现场)
return res;
}
};


20小时前
class Solution {
public:
int maxVowels(string s, int k) {
int res = 0;
unordered_set<char> hash({'a','e','i','o','u'});
for(int i=0,cnt=0;i<s.size();++i)
{
cnt += hash.count(s[i]);
if(i>=k) cnt -= hash.count(s[i-k]);
if(i>=k-1) res = max(res,cnt);
}
return res;
}
};


20小时前
class Solution {
public:
int isPrefixOfWord(string sentence, string searchWord) {
stringstream ssin(sentence);

string word;
for(int i=1;ssin>>word;++i)
{
if(word.substr(0,searchWord.size()) == searchWord)
return i;
}
return -1;

}
};


class Solution {
public:
vector<int> peopleIndexes(vector<vector<string>>& s) {
int n = s.size();
for(auto &e:s) sort(e.begin(),e.end()); //先排序，方便后续比较

vector<int>res;
for(int i=0;i<n;++i)
{
bool is_lll = false;
for(int j=0;j<n;++j)
{
if(i!=j)
{
auto&A = s[i],&B = s[j];
int a=0;
for(int b = 0;b<B.size()&&a<A.size();++b)
if(A[a] == B[b])
a++;

if(a == A.size())
{
is_lll =true;
break;
}
}
}
if(!is_lll) res.push_back(i);
}
return res;
}
};


class Solution {
public:
int busyStudent(vector<int>& startTime, vector<int>& endTime, int queryTime) {
int res = 0;
for(int i=0;i<startTime.size();++i)
{
if(queryTime>=startTime[i] && queryTime<=endTime[i])
res++;
}
return res;
}
};


class Solution {
public:
string arrangeWords(string text) {
stringstream ssin(text);
vector<string > words;
string word;
while(ssin>>word) words.push_back(word);
words[0][0] = tolower(words[0][0]);
stable_sort(words.begin(),words.end(),[](string a,string b){
return a.size()<b.size();
});
words[0][0] = toupper(words[0][0]);

string res;
for(auto e:words)
{
res = res+= e + " ";
}
res.pop_back();
return res;
}
};


#include<iostream>
using namespace std;

int exgcd(int a,int b,int&x,int&y)
{
if(!b)
{
x=1,y=0;
return a;
}

int d = exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}

int main()
{
int n;
cin>>n;
while(n--)
{
int a,b;
cin>>a>>b;
int x,y;

exgcd(a,b,x,y);

cout<<x<<" "<<y<<endl;
}
return 0;
}


#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;

LL pmi(int a,int k,int p)
{
LL res = 1%p;
while(k)
{
if(k&1) res= res*a%p;
k>>=1;
a = (LL)a*a%p;
}
return res;
}

int main()
{
int n;
cin>>n;
while(n--)
{
int a,p;
cin>>a>>p;
int res = pmi(a,p-2,p);
if(a%p) cout<<res<<endl;
else cout<<"impossible"<<endl;
}
return 0;
}


#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;

LL pmi(int a,int k,int p)
{
LL res = 1%p;
while(k)
{
if(k&1) res= res*a%p;
k>>=1;
a = (LL)a*a%p;
}
return res;
}

int main()
{
int n;
cin>>n;
while(n--)
{
int a,k,p;
cin>>a>>k>>p;
printf("%d\n",pmi(a,k,p));
}
return 0;
}


#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;

const int  N =1000010;
int primes[N],cnt;
bool st[N];
int res[N];

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

LL num = 0;
for(int i=1;i<=n;++i) num+=res[i];
return num;
}
int main()
{
int n;
cin>>n;

cout<<get(n)<<endl;

return 0;
}