首页 > 其他分享 >P4780 Phi的反函数 题解

P4780 Phi的反函数 题解

时间:2024-09-24 21:14:43浏览次数:10  
标签:10 Phi frac cout 剪枝 int 题解 P4780 因子

因为 \(\varphi(x)\) 的值只与 \(x\) 的不同质因子有关,又因为 \(2^{31}\) 之内的数的质因子个数不超过 \(10\),所以容易枚举 \(10\) 个位置上填入的质因子打出朴素的暴力,简单剪枝后得到 \(20\) 分。

注意需要先判掉 \(x = n + 1\) 的情况。

考虑优化:因为 \(\varphi\) 的值只与质因子有关(而不是质因子幂次),所以不用重复填入质因子,得到 \(68\) 分。

此时 \(x\) 可以表示为不同质数的乘积,设为 \(x = p_1 p_2 p_3 \cdots p_m\),则

\[\begin{align*} \varphi(x) &= x \frac {p_1 - 1} {p_1} \frac {p_2 - 1} {p_2} \frac {p_3 - 1} {p_3} \cdots \frac {p_m - 1} {p_m} \\ &= (p_1 - 1) (p_2 - 1) (p_3 - 1) \cdots (p_m - 1) \\ \end{align*} \]

即 \(\forall i \in [1, m]\),有 \((p_i - 1) \mid n\),用这个剪枝即可。

剪枝后,搜索实际上是枚举选 / 不选质因子,时间复杂度 \(O(2^{\omega(n)} \sqrt n)\)。

实际实现中可以筛出一定范围内的质数,达到 \(O(2^{\omega(n)})\) 的时间复杂度,本题筛到 \(2 \cdot 10^5\) 即可通过。

#include <iostream>

#define int long long

using namespace std;

const int lim = 2e5;
const int mxx = 1ll << 31;

bool vis[lim + 5];
int pr[lim + 5], tail;

int n;

static inline bool isprime(int x) {
    for (int i = 2; i * i <= x; ++i)
        if (x % i == 0)
            return false;
    return true;
}

int ans = mxx + 1;

static inline void dfs(int x, int ph, int las, int dep) {
    if (ph > n)
        return;
    if (x >= ans)
        return;
    if (ph == n)
        ans = x;
    if (n % ph)
        return;
    if (dep < 10)
        for (int i = 1; i < las; ++i)
            dfs(x * pr[i], ph * (pr[i] - 1), i, dep + 1);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for (int i = 2; i <= lim; ++i) {
        if (!vis[i])
            pr[++tail] = i;
        for (int j = 1; j <= tail && i * pr[j] <= lim; ++j) {
            vis[i * pr[j]] = true;
            if (i % pr[j] == 0)
                break;
        }
    }
    cin >> n;
    if (n == 1) {
        cout << 1 << endl;
        return 0;
    }
    if (isprime(n + 1)) {
        cout << n + 1 << endl;
        return 0;
    }
    dfs(1, 1, tail, 1);
    if (ans > mxx)
        cout << -1 << endl;
    else
        cout << ans << endl;
    return 0;
}

标签:10,Phi,frac,cout,剪枝,int,题解,P4780,因子
From: https://www.cnblogs.com/bluewindde/p/18430024

相关文章

  • Codeforces Round 959 (Div. 1 + Div. 2) C. Hungry Games题解
    CodeforcesRound959(Div.1+Div.2)C.HungryGames题解题目链接大致题意:给定一个长度为n的数组,并且给出一对l,r表示一个区间,如果∑i......
  • 力扣题解2207
    大家好,欢迎来到无限大的频道。今日继续给大家带来力扣题解。题目描述(中等)​:字符串中最多数目的子序列给你一个下标从 0 开始的字符串 text 和另一个下标从 0 开始且长度为 2 的字符串 pattern ,两者都只包含小写英文字母。你可以在 text 中任意位置插入 一个......
  • 【洛谷】P2261 [CQOI2007] 余数求和 的题解
    【洛谷】P2261[CQOI2007]余数求和的题解洛谷传送门题解这还是蓝题,这还是省选qaq题目看着很简单,但是真的很考验思路,思路对了,代码不到555分钟写完。刚开始做的时......
  • 题解:SP1741 TETRIS3D - Tetris 3D
    题意维护一个\(D\timesS\)的平面,每个点有一个高度。要求支持一个操作:查询一个矩形区域的最大值,并将该区域更新为最大值加上给定的数。分析发现\(D,S\leq10^3\),考虑使用二维线段树维护。二维线段树,顾名思义,就是在普通线段树的每一个节点上维护一棵线段树。在本题中,外层节......
  • 题解:P10950 太鼓达人
    分析显然答案包含长度为\(K\)的所有\(01\)串,每个串和前一个的重叠长度为\(K-1\),所以每个串对长度的贡献为\(1\)。因此该串的长度为所有\(01\)串的个数,即\(2^K\)。考虑第二个如何解决。发现每个位置的状态只有\(0\)和\(1\),考虑爆搜。显然直接搜的复杂度为\(O(2^......
  • 题解:P5184 [COCI2009-2010#2] PASIJANS
    分析考虑贪心,每次尽量选最小的字符。显然是每次选字典序最小的弹栈。我们要比较的是每个栈的字典序,但是朴素比较是\(O(L)\)的,考虑将它优化到\(O(1)\)。这个时候我们可以先离散化然后套路地将所有串拼一起跑SA。记得在每个串之间加分割符。这样每次比较字典序就变成了\(......
  • 题解:P6351 [PA2011] Hard Choice
    题意维护一张无向图,要求支持以下操作:切断一条边。查询两个点是否有有两条完全不同的路径相连。分析因为断边操作不好维护,考虑离线后将断边变为加边。因此,我们只需要维护加边操作即可。考虑使用LCT。首先,因为涉及到边权,套路地用节点代替边。如果某一条边连接的两个点......
  • ABC245G Foreign Friends 题解 / 二进制分组
    ABC245GForeignFriends题解回顾一下二进制分组。题目大意给定一张\(N\)个点\(M\)条边的无向图,及\(L\)个特殊点。每个点有颜色\(C_i\)。求每个点到离他最近的与他颜色不同特殊点的距离。Solve两个点颜色不同,等价于他们的颜色在二进制下至少有一位不同。所以我们考......
  • MySQL GROUP BY 分区大小写问题解析
    在数据库操作中,GROUPBY是一个常用的SQL语句,用于根据一个或多个列的值对结果集进行分组。然而,在使用MySQL时,你可能会遇到一个常见问题:大小写敏感性。本文将探讨MySQL中GROUPBY的大小写敏感性问题,并提供一些解决方案。什么是大小写敏感性?在计算机科学中,大小写敏感性是指......
  • Codeforces Round 974 (Div.3) 题解
    CodeforcesRound974(Div.3)题解A.RobinHelps模拟按照题意模拟即可。voidShowball(){intn,k;cin>>n>>k;intcur=0,ans=0;for(inti=0;i<n;i++){intx;cin>>x;if(x>=k)cur+=x;elseif(!x){if(cur>=1)cu......