牛客多校，第四场。
若有公式图片无法正常显示，请使用梯子访问！
B - Basic Gcd Problem
- 题意:
定义函数如下：
给出,求
.
- 思路:
这个题虽然过了 但是源代码写的很垃圾，结束后发现能优化不少呢
(本题题解思路源自我同学的blog，写的很好！见LDH的blog)
首先分析下这个公式，大概就是一个 ci乘一个会迭代的函数 ，直到迭代到 x=1 时结束。迭代过程如下：
观察发现每次迭代都会乘上ci的值，所以迭代n次就有n个ci相乘，即为c的n次方，那么就是求解迭代次数即可，每次迭代取当前x的最小非互质数，这样才能保证 gcd(i,x) 的值最大，使能够迭代的次数尽可能多。
//原文链接：https://blog.csdn.net/NGUP_LEE/article/details/107498007
const int mod = 1e9 + 7;
#define ll long long
ll qpow(ll x,ll y,ll mod)
{
ll res=1;
while(y)
{
if(y&1) res=(res*x)%mod;
x=(x*x)%mod;
y>>=1;
}
return (res+mod)%mod;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--)
{
int cnt=0;
int n,c;
cin>>n>>c;
for(int i=2;i*i<=n;i++)//求解迭代次数cnt
{
while (n%i==0)
{
cnt++;
n/=i;
}
}
if(n>1) cnt++;
ll ans=qpow(c,cnt,mod);
cout<<ans<<"\n";
}
return 0;
}
H - Harder Gcd Problem
-
题意:
将1~n的数两两匹配，匹配要求两数gcd(a,b)>1，求最大的匹配对数与匹配过程。 -
思路:
- gcd(a,b)>1即为两数不互质。
- 因为所有的非质数都可以由某一质数的倍数表示出来，所以先打一遍素数表，这里需要将素数作为下标存入，便于直接访问。
- 采取贪心的思路，从大的质数开始匹配。匹配即为取当前质数的倍数们进行两两配对。
- 如果当前质数的倍数数量为奇数也不用担心，直接匹配就行，剩余的单个数不用管，因为在匹配质数“2”的倍数时一定会处理到这个数，因为奇数与偶数的倍数都是偶数，即2的倍数。（这是网上大多数博主的错误，这个奇数个数的匹配并不用特殊处理！！！）
const int N = 100010;
bool notprime[N];
int prime[N];
int pn;
int n;
bool vis[N];
vector<pair<ll, ll>> ans;
//素数筛，素数作为下标存入。
void GetPrime()
{
pn = 0;
notprime[1] = 1;
int i;
for (i = 2; i < N; i++)
{
if (notprime[i] == false)
prime[pn++] = i;
for (int j = 0; j < pn && prime[j] * i < N; j++)
{
notprime[prime[j] * i] = true;
if (i % prime[j] == 0)
break;
}
}
}
int main()
{
GetPrime();
int T;
cin >> T;
while (T--)
{
cin >> n;
ans.clear();
for (int i = 2; i <= n; i++)
vis[i] = 0;
for (int i = n; i >= 2; i--)
{
if (notprime[i] == true)
continue;
int pri_now = i;
int max_time = (n / i) * i;
for (int j = max_time; j > i; j = j - i)
{
if (vis[j])
continue;
if (pri_now == -1)
pri_now = j;
else
{
ans.push_back(make_pair(pri_now, j));
vis[pri_now] = 1;
vis[j] = 1;
pri_now = -1;
}
}
}
cout << ans.size() << endl;
for (int i = 0; i < ans.size(); i++)
cout << ans[i].first << " " << ans[i].second << '\n';
}
return 0;
}