Автокомментарий: текст был обновлен пользователем Gornak40 (предыдущая версия, новая версия, сравнить).

Auto comment: topic has been updated by Gornak40 (previous revision, new revision, compare).

You haven't declared any of the fixed registers you clobber with this code, so it's terrible undefined behavior: If the compiler was using rax for anything you are toast. Also, 64-bit idiv is very slow on some systems: You may find a floating-point-based method much faster. (And for hashing applications you can probably use Montgomery reduction instead of "ordinary" modmul for even better performance.)

I see a few problems with this code:

• Codeforces runs on Windows, so rbx should be preserved (source), otherwise it may cause troubles when combined with GCC-generated code.
• The assembly causes many things to be moved around often if you see the compiled code, making it inefficient.
  • If you want to write an entire function in asm, I suggest using GCC's __attribute__((naked)) (source).
• Integer division instructions are very slow, and dividing by a constant can be optimized a lot. You can find many resources for fast division on Codeforces (like this blog or this).

That being said, using x86 instructions directly is significantly faster than running __int128 division (which calls a large, slower function __modti3) when you only need 64 bits of modulus and output.

Here is my version of the function in assembly (Windows call convention):

__attribute__((naked)) long long modmul(long long, long long, long long) {
    asm(R"(
        mov %rcx, %rax
        imul %rdx
        idiv %r8
        mov %rdx, %rax
        ret
    )");
}

__attribute__((naked)) long long modmul(long long, long long, long long) {
    asm(R"(
        mov %rdi, %rax
        mov %rdx, %rcx
        imul %rsi
        idiv %rcx
        mov %rdx, %rax
        ret
    )");
}

Codeforces has the gym named "Fast modular multiplication", where I have tested how fast the assembler insertion is.

//                                         RCX,      RDX,       R8 
__attribute__((naked)) uint64_t mulmod64(uint64_t, uint64_t, uint64_t) 
{
    asm(R"(
        .intel_syntax noprefix
        mov rax, rcx
        mul rdx
        div r8
        mov rax, rdx
        ret
        .att_syntax noprefix
    )");
}
 
uint64_t prod(const test& t)
{
    return mulmod64(t.x, t.y, t.modulo);
}

uint64_t prod(const test& t)
{
    return uint64_t((unsigned __int128)t.x * t.y % t.modulo);
}

So, the assembler insertion is slightly faster, but not significantly faster.

If you really need int64 multiplication, better consider this variant:

using uint64 = unsigned long long;
uint64 modmul(uint64 a, uint64 b, uint64 M) {
	ll ret = a * b - M * uint64(1.L / M * a * b);
	return ret + M * (ret < 0) - M * (ret >= (ll)M);
}

There is a proof that it works here: https://github.com/kth-competitive-programming/kactl/blob/main/doc/modmul-proof.pdf

This is much faster, and is not correct only for some int64 values, that are almost certainly much bigger than any modulo you choose